cholmod_modify.h
Go to the documentation of this file.00001 /* ========================================================================== */ 00002 /* === Include/cholmod_modify.h ============================================= */ 00003 /* ========================================================================== */ 00004 00005 /* ----------------------------------------------------------------------------- 00006 * CHOLMOD/Include/cholmod_modify.h. 00007 * Copyright (C) 2005-2006, Timothy A. Davis and William W. Hager 00008 * CHOLMOD/Include/cholmod_modify.h is licensed under Version 2.0 of the GNU 00009 * General Public License. See gpl.txt for a text of the license. 00010 * CHOLMOD is also available under other licenses; contact authors for details. 00011 * http://www.cise.ufl.edu/research/sparse 00012 * -------------------------------------------------------------------------- */ 00013 00014 /* CHOLMOD Modify module. 00015 * 00016 * Sparse Cholesky modification routines: update / downdate / rowadd / rowdel. 00017 * Can also modify a corresponding solution to Lx=b when L is modified. This 00018 * module is most useful when applied on a Cholesky factorization computed by 00019 * the Cholesky module, but it does not actually require the Cholesky module. 00020 * The Core module can create an identity Cholesky factorization (LDL' where 00021 * L=D=I) that can then by modified by these routines. 00022 * 00023 * Primary routines: 00024 * ----------------- 00025 * 00026 * cholmod_updown multiple rank update/downdate 00027 * cholmod_rowadd add a row to an LDL' factorization 00028 * cholmod_rowdel delete a row from an LDL' factorization 00029 * 00030 * Secondary routines: 00031 * ------------------- 00032 * 00033 * cholmod_updown_solve update/downdate, and modify solution to Lx=b 00034 * cholmod_updown_mark update/downdate, and modify solution to partial Lx=b 00035 * cholmod_updown_mask update/downdate for LPDASA 00036 * cholmod_rowadd_solve add a row, and update solution to Lx=b 00037 * cholmod_rowadd_mark add a row, and update solution to partial Lx=b 00038 * cholmod_rowdel_solve delete a row, and downdate Lx=b 00039 * cholmod_rowdel_mark delete a row, and downdate solution to partial Lx=b 00040 * 00041 * Requires the Core module. Not required by any other CHOLMOD module. 00042 */ 00043 00044 #ifndef CHOLMOD_MODIFY_H 00045 #define CHOLMOD_MODIFY_H 00046 00047 #include "cholmod_core.h" 00048 00049 /* -------------------------------------------------------------------------- */ 00050 /* cholmod_updown: multiple rank update/downdate */ 00051 /* -------------------------------------------------------------------------- */ 00052 00053 /* Compute the new LDL' factorization of LDL'+CC' (an update) or LDL'-CC' 00054 * (a downdate). The factor object L need not be an LDL' factorization; it 00055 * is converted to one if it isn't. */ 00056 00057 int cholmod_updown 00058 ( 00059 /* ---- input ---- */ 00060 int update, /* TRUE for update, FALSE for downdate */ 00061 cholmod_sparse *C, /* the incoming sparse update */ 00062 /* ---- in/out --- */ 00063 cholmod_factor *L, /* factor to modify */ 00064 /* --------------- */ 00065 cholmod_common *Common 00066 ) ; 00067 00068 int cholmod_l_updown (int, cholmod_sparse *, cholmod_factor *, 00069 cholmod_common *) ; 00070 00071 /* -------------------------------------------------------------------------- */ 00072 /* cholmod_updown_solve: update/downdate, and modify solution to Lx=b */ 00073 /* -------------------------------------------------------------------------- */ 00074 00075 /* Does the same as cholmod_updown, except that it also updates/downdates the 00076 * solution to Lx=b+DeltaB. x and b must be n-by-1 dense matrices. b is not 00077 * need as input to this routine, but a sparse change to b is (DeltaB). Only 00078 * entries in DeltaB corresponding to columns modified in L are accessed; the 00079 * rest must be zero. */ 00080 00081 int cholmod_updown_solve 00082 ( 00083 /* ---- input ---- */ 00084 int update, /* TRUE for update, FALSE for downdate */ 00085 cholmod_sparse *C, /* the incoming sparse update */ 00086 /* ---- in/out --- */ 00087 cholmod_factor *L, /* factor to modify */ 00088 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00089 cholmod_dense *DeltaB, /* change in b, zero on output */ 00090 /* --------------- */ 00091 cholmod_common *Common 00092 ) ; 00093 00094 int cholmod_l_updown_solve (int, cholmod_sparse *, cholmod_factor *, 00095 cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00096 00097 /* -------------------------------------------------------------------------- */ 00098 /* cholmod_updown_mark: update/downdate, and modify solution to partial Lx=b */ 00099 /* -------------------------------------------------------------------------- */ 00100 00101 /* Does the same as cholmod_updown_solve, except only part of L is used in 00102 * the update/downdate of the solution to Lx=b. This routine is an "expert" 00103 * routine. It is meant for use in LPDASA only. See cholmod_updown.c for 00104 * a description of colmark. */ 00105 00106 int cholmod_updown_mark 00107 ( 00108 /* ---- input ---- */ 00109 int update, /* TRUE for update, FALSE for downdate */ 00110 cholmod_sparse *C, /* the incoming sparse update */ 00111 int *colmark, /* int array of size n. See cholmod_updown.c */ 00112 /* ---- in/out --- */ 00113 cholmod_factor *L, /* factor to modify */ 00114 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00115 cholmod_dense *DeltaB, /* change in b, zero on output */ 00116 /* --------------- */ 00117 cholmod_common *Common 00118 ) ; 00119 00120 int cholmod_l_updown_mark (int, cholmod_sparse *, UF_long *, cholmod_factor *, 00121 cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00122 00123 /* -------------------------------------------------------------------------- */ 00124 /* cholmod_updown_mask: update/downdate, for LPDASA */ 00125 /* -------------------------------------------------------------------------- */ 00126 00127 /* Does the same as cholmod_updown_mark, except has an additional "mask" 00128 * argument. This routine is an "expert" routine. It is meant for use in 00129 * LPDASA only. See cholmod_updown.c for a description of mask. */ 00130 00131 int cholmod_updown_mask 00132 ( 00133 /* ---- input ---- */ 00134 int update, /* TRUE for update, FALSE for downdate */ 00135 cholmod_sparse *C, /* the incoming sparse update */ 00136 int *colmark, /* int array of size n. See cholmod_updown.c */ 00137 int *mask, /* size n */ 00138 /* ---- in/out --- */ 00139 cholmod_factor *L, /* factor to modify */ 00140 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00141 cholmod_dense *DeltaB, /* change in b, zero on output */ 00142 /* --------------- */ 00143 cholmod_common *Common 00144 ) ; 00145 00146 int cholmod_l_updown_mask (int, cholmod_sparse *, UF_long *, UF_long *, 00147 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00148 00149 /* -------------------------------------------------------------------------- */ 00150 /* cholmod_rowadd: add a row to an LDL' factorization (a rank-2 update) */ 00151 /* -------------------------------------------------------------------------- */ 00152 00153 /* cholmod_rowadd adds a row to the LDL' factorization. It computes the kth 00154 * row and kth column of L, and then updates the submatrix L (k+1:n,k+1:n) 00155 * accordingly. The kth row and column of L must originally be equal to the 00156 * kth row and column of the identity matrix. The kth row/column of L is 00157 * computed as the factorization of the kth row/column of the matrix to 00158 * factorize, which is provided as a single n-by-1 sparse matrix R. */ 00159 00160 int cholmod_rowadd 00161 ( 00162 /* ---- input ---- */ 00163 size_t k, /* row/column index to add */ 00164 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 00165 /* ---- in/out --- */ 00166 cholmod_factor *L, /* factor to modify */ 00167 /* --------------- */ 00168 cholmod_common *Common 00169 ) ; 00170 00171 int cholmod_l_rowadd (size_t, cholmod_sparse *, cholmod_factor *, 00172 cholmod_common *) ; 00173 00174 /* -------------------------------------------------------------------------- */ 00175 /* cholmod_rowadd_solve: add a row, and update solution to Lx=b */ 00176 /* -------------------------------------------------------------------------- */ 00177 00178 /* Does the same as cholmod_rowadd, and also updates the solution to Lx=b 00179 * See cholmod_updown for a description of how Lx=b is updated. There is on 00180 * additional parameter: bk specifies the new kth entry of b. */ 00181 00182 int cholmod_rowadd_solve 00183 ( 00184 /* ---- input ---- */ 00185 size_t k, /* row/column index to add */ 00186 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 00187 double bk [2], /* kth entry of the right-hand-side b */ 00188 /* ---- in/out --- */ 00189 cholmod_factor *L, /* factor to modify */ 00190 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00191 cholmod_dense *DeltaB, /* change in b, zero on output */ 00192 /* --------------- */ 00193 cholmod_common *Common 00194 ) ; 00195 00196 int cholmod_l_rowadd_solve (size_t, cholmod_sparse *, double *, 00197 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00198 00199 /* -------------------------------------------------------------------------- */ 00200 /* cholmod_rowadd_mark: add a row, and update solution to partial Lx=b */ 00201 /* -------------------------------------------------------------------------- */ 00202 00203 /* Does the same as cholmod_rowadd_solve, except only part of L is used in 00204 * the update/downdate of the solution to Lx=b. This routine is an "expert" 00205 * routine. It is meant for use in LPDASA only. */ 00206 00207 int cholmod_rowadd_mark 00208 ( 00209 /* ---- input ---- */ 00210 size_t k, /* row/column index to add */ 00211 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 00212 double bk [2], /* kth entry of the right hand side, b */ 00213 int *colmark, /* int array of size n. See cholmod_updown.c */ 00214 /* ---- in/out --- */ 00215 cholmod_factor *L, /* factor to modify */ 00216 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00217 cholmod_dense *DeltaB, /* change in b, zero on output */ 00218 /* --------------- */ 00219 cholmod_common *Common 00220 ) ; 00221 00222 int cholmod_l_rowadd_mark (size_t, cholmod_sparse *, double *, UF_long *, 00223 cholmod_factor *, cholmod_dense *, cholmod_dense *, 00224 cholmod_common *) ; 00225 00226 /* -------------------------------------------------------------------------- */ 00227 /* cholmod_rowdel: delete a row from an LDL' factorization (a rank-2 update) */ 00228 /* -------------------------------------------------------------------------- */ 00229 00230 /* Sets the kth row and column of L to be the kth row and column of the identity 00231 * matrix, and updates L(k+1:n,k+1:n) accordingly. To reduce the running time, 00232 * the caller can optionally provide the nonzero pattern (or an upper bound) of 00233 * kth row of L, as the sparse n-by-1 vector R. Provide R as NULL if you want 00234 * CHOLMOD to determine this itself, which is easier for the caller, but takes 00235 * a little more time. 00236 */ 00237 00238 int cholmod_rowdel 00239 ( 00240 /* ---- input ---- */ 00241 size_t k, /* row/column index to delete */ 00242 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 00243 /* ---- in/out --- */ 00244 cholmod_factor *L, /* factor to modify */ 00245 /* --------------- */ 00246 cholmod_common *Common 00247 ) ; 00248 00249 int cholmod_l_rowdel (size_t, cholmod_sparse *, cholmod_factor *, 00250 cholmod_common *) ; 00251 00252 /* -------------------------------------------------------------------------- */ 00253 /* cholmod_rowdel_solve: delete a row, and downdate Lx=b */ 00254 /* -------------------------------------------------------------------------- */ 00255 00256 /* Does the same as cholmod_rowdel, but also downdates the solution to Lx=b. 00257 * When row/column k of A is "deleted" from the system A*y=b, this can induce 00258 * a change to x, in addition to changes arising when L and b are modified. 00259 * If this is the case, the kth entry of y is required as input (yk) */ 00260 00261 int cholmod_rowdel_solve 00262 ( 00263 /* ---- input ---- */ 00264 size_t k, /* row/column index to delete */ 00265 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 00266 double yk [2], /* kth entry in the solution to A*y=b */ 00267 /* ---- in/out --- */ 00268 cholmod_factor *L, /* factor to modify */ 00269 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00270 cholmod_dense *DeltaB, /* change in b, zero on output */ 00271 /* --------------- */ 00272 cholmod_common *Common 00273 ) ; 00274 00275 int cholmod_l_rowdel_solve (size_t, cholmod_sparse *, double *, 00276 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00277 00278 /* -------------------------------------------------------------------------- */ 00279 /* cholmod_rowdel_mark: delete a row, and downdate solution to partial Lx=b */ 00280 /* -------------------------------------------------------------------------- */ 00281 00282 /* Does the same as cholmod_rowdel_solve, except only part of L is used in 00283 * the update/downdate of the solution to Lx=b. This routine is an "expert" 00284 * routine. It is meant for use in LPDASA only. */ 00285 00286 int cholmod_rowdel_mark 00287 ( 00288 /* ---- input ---- */ 00289 size_t k, /* row/column index to delete */ 00290 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 00291 double yk [2], /* kth entry in the solution to A*y=b */ 00292 int *colmark, /* int array of size n. See cholmod_updown.c */ 00293 /* ---- in/out --- */ 00294 cholmod_factor *L, /* factor to modify */ 00295 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 00296 cholmod_dense *DeltaB, /* change in b, zero on output */ 00297 /* --------------- */ 00298 cholmod_common *Common 00299 ) ; 00300 00301 int cholmod_l_rowdel_mark (size_t, cholmod_sparse *, double *, UF_long *, 00302 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 00303 00304 #endif