MADlib
0.7 A newer version is available
User Documentation
|
00001 /* ----------------------------------------------------------------------- *//** 00002 * 00003 * @file conjugate_gradient.sql_in 00004 * 00005 * @brief SQL function computing Conjugate Gradient 00006 * @date March 2011 00007 * 00008 * 00009 *//* ----------------------------------------------------------------------- */ 00010 00011 /** 00012 @addtogroup grp_cg 00013 00014 @about 00015 This function uses the iterative conjugate gradient method [1] to find a solution to the function: \f[ \boldsymbol Ax = \boldsymbol b \f] 00016 where \f$ \boldsymbol A \f$ is a symmetric, positive definite matrix and \f$x\f$ and \f$ \boldsymbol b \f$ are vectors. 00017 00018 @input 00019 Matrix \f$ \boldsymbol A \f$ is assumed to be stored in a table where each row consists of at least two columns: array containing values of a given row, row number: 00020 <pre>{TABLE|VIEW} <em>matrix_A</em> ( 00021 <em>row_number</em> FLOAT, 00022 <em>row_values</em> FLOAT[], 00023 )</pre> 00024 The number of elements in each row should be the same. 00025 00026 \f$ \boldsymbol b \f$ is passed as a FLOAT[] to the function. 00027 00028 @usage 00029 Conjugate gradient can be called as follows: 00030 <pre>SELECT \ref conjugate_gradient('<em>table_name</em>', 00031 '<em>name_of_row_values_col</em>', '<em>name_of_row_number_col</em>', '<em>aray_of_b_values</em>', 00032 '<em>desired_precision</em>');</pre> 00033 Function returns x as an array. 00034 00035 @examp 00036 -# Construct matrix A according to structure: 00037 \code 00038 sql> SELECT * FROM data; 00039 row_num | row_val 00040 ---------+--------- 00041 1 | {2,1} 00042 2 | {1,4} 00043 (2 rows) 00044 \endcode 00045 -# Call conjugate gradient function: 00046 \code 00047 sql> SELECT conjugate_gradient('data','row_val','row_num','{2,1}',1E-6,1); 00048 INFO: COMPUTE RESIDUAL ERROR 14.5655661859659 00049 INFO: ERROR 0.144934004246004 00050 INFO: ERROR 3.12963615962926e-31 00051 INFO: TEST FINAL ERROR 2.90029642185163e-29 00052 conjugate_gradient 00053 --------------------------- 00054 {1,-1.31838984174237e-15} 00055 (1 row) 00056 \endcode 00057 00058 @literature 00059 [1] "Conjugate gradient method" Wikipedia - http://en.wikipedia.org/wiki/Conjugate_gradient_method 00060 00061 @sa File conjugate_gradient.sql_in documenting the SQL function. 00062 */ 00063 00064 /** 00065 * @brief Compute conjugate gradient 00066 * 00067 * @param matrix Name of the table containing argument matrix A 00068 * @param val_id Name of the column contains row values 00069 * @param row_id Name of the column contains row number 00070 * @param b Array containing values of b 00071 * @param precision_limit Precision threshold after which process will terminate 00072 * @param verbosity Verbose flag (0 = false, 1 = true) 00073 * @returns Array containing values of x 00074 * 00075 */ 00076 CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.conjugate_gradient(Matrix TEXT, val_id TEXT, row_id TEXT, b FLOAT[], precision_limit FLOAT, verbosity INT) RETURNS FLOAT[] AS $$ 00077 declare 00078 r FLOAT[]; 00079 p FLOAT[]; 00080 x FLOAT[]; 00081 k INT; 00082 iter INT = 0; 00083 recidual_refresh INT := 30; 00084 alpha FLOAT; 00085 r_size FLOAT; 00086 r_new_size FLOAT; 00087 Ap FLOAT[]; 00088 Ax FLOAT[]; 00089 pAp_size FLOAT; 00090 beta FLOAT; 00091 exit_if_no_progess_in INT := 15; 00092 begin 00093 DROP TABLE IF EXISTS X_val; 00094 CREATE TEMP TABLE X_val( 00095 value FLOAT[] 00096 ); 00097 00098 DROP TABLE IF EXISTS P_val; 00099 CREATE TEMP TABLE P_val( 00100 value FLOAT[] 00101 ); 00102 00103 SELECT INTO k array_upper(b,1); 00104 --INSERT INTO X_val SELECT ARRAY(SELECT random() FROM generate_series(1, k)); 00105 EXECUTE 'INSERT INTO X_val SELECT ARRAY(SELECT random() FROM generate_series(1,' ||k|| '))'; 00106 LOOP 00107 IF(iter%recidual_refresh = 0)THEN 00108 EXECUTE 'SELECT ARRAY(SELECT MADLIB_SCHEMA.array_dot('||val_id||', j.x) FROM (SELECT value AS x FROM X_val) AS j, '|| Matrix ||' ORDER BY '||row_id||' LIMIT '|| k ||')' INTO Ax; 00109 SELECT INTO r MADLIB_SCHEMA.array_sub(b, Ax); 00110 SELECT INTO r_size MADLIB_SCHEMA.array_dot(r, r); 00111 IF(verbosity > 0) THEN 00112 RAISE INFO 'COMPUTE RESIDUAL ERROR %', r_size; 00113 END IF; 00114 SELECT INTO p r; 00115 END IF; 00116 iter = iter + 1; 00117 TRUNCATE TABLE P_val; 00118 --INSERT INTO P_val VALUES(p); 00119 EXECUTE 'INSERT INTO P_val(value) VALUES(array['|| array_to_string(p,',') ||'])'; 00120 EXECUTE 'SELECT ARRAY(SELECT MADLIB_SCHEMA.array_dot('||val_id||', j.p) FROM (SELECT value AS p FROM P_val) AS j,'|| Matrix ||' ORDER BY '||row_id||' LIMIT '|| k ||')' INTO Ap; 00121 SELECT INTO pAp_size MADLIB_SCHEMA.array_dot(p, Ap); 00122 alpha = r_size/pAp_size; 00123 00124 --SELECT INTO x MADLIB_SCHEMA.array_add(value, MADLIB_SCHEMA.array_scalar_mult(p,alpha)) FROM X_val; 00125 EXECUTE 'SELECT MADLIB_SCHEMA.array_add(value, MADLIB_SCHEMA.array_scalar_mult(array['|| array_to_string(p,',') ||']::float[],'||alpha||'::float)) FROM X_val' INTO x; 00126 TRUNCATE TABLE X_val; 00127 --INSERT INTO X_val VALUES(x); 00128 EXECUTE 'INSERT INTO X_val VALUES(array['|| array_to_string(x,',') ||'])'; 00129 00130 SELECT INTO r MADLIB_SCHEMA.array_add(r,MADLIB_SCHEMA.array_scalar_mult(Ap, -alpha)); 00131 SELECT INTO r_new_size MADLIB_SCHEMA.array_dot(r,r); 00132 00133 IF(verbosity > 0) THEN 00134 RAISE INFO 'ERROR %',r_new_size; 00135 END IF; 00136 IF (r_new_size < precision_limit) THEN 00137 EXECUTE 'SELECT ARRAY(SELECT MADLIB_SCHEMA.array_dot('||val_id||', j.x) FROM (SELECT value AS x FROM X_val) AS j, '|| Matrix ||' ORDER BY '||row_id||' LIMIT '|| k ||')' INTO Ax; 00138 SELECT INTO r MADLIB_SCHEMA.array_sub(b, Ax); 00139 SELECT INTO r_new_size MADLIB_SCHEMA.array_dot(r, r); 00140 IF(verbosity > 0) THEN 00141 RAISE INFO 'TEST FINAL ERROR %', r_new_size; 00142 END IF; 00143 IF (r_new_size < precision_limit) THEN 00144 EXIT; 00145 END IF; 00146 END IF; 00147 SELECT INTO p MADLIB_SCHEMA.array_add(r, MADLIB_SCHEMA.array_scalar_mult(p, r_new_size/r_size)); 00148 IF(r_size < r_new_size) THEN 00149 exit_if_no_progess_in = exit_if_no_progess_in-1; 00150 RAISE INFO 'No progress! count = %',exit_if_no_progess_in; 00151 00152 IF(exit_if_no_progess_in <= 0) THEN 00153 RAISE EXCEPTION 'Algorithm failed to converge. Check is input is positive definate.'; 00154 END IF; 00155 ELSE 00156 exit_if_no_progess_in = 15; 00157 END IF; 00158 r_size = r_new_size; 00159 END LOOP; 00160 IF(verbosity > 1) THEN 00161 RETURN ARRAY[r_new_size]; 00162 END IF; 00163 --SELECT INTO x value FROM X_val; 00164 EXECUTE 'SELECT value FROM X_val' INTO x; 00165 RETURN x; 00166 end 00167 $$ LANGUAGE plpgsql; 00168 00169 CREATE OR REPLACE FUNCTION MADLIB_SCHEMA.conjugate_gradient(Matrix TEXT, val_id TEXT, row_id TEXT, b FLOAT[], precision_limit FLOAT) RETURNS FLOAT[] AS $$ 00170 declare 00171 begin 00172 RETURN MADLIB_SCHEMA.conjugate_gradient(Matrix, val_id, row_id, b, precision_limit,0); 00173 end 00174 $$ LANGUAGE plpgsql;