1 /* ========================================================================== */ 2 /* === Include/cholmod_modify.h ============================================= */ 3 /* ========================================================================== */ 4 5 /* ----------------------------------------------------------------------------- 6 * CHOLMOD/Include/cholmod_modify.h. 7 * Copyright (C) 2005-2006, Timothy A. Davis and William W. Hager 8 * http://www.suitesparse.com 9 * -------------------------------------------------------------------------- */ 10 11 /* CHOLMOD Modify module. 12 * 13 * Sparse Cholesky modification routines: update / downdate / rowadd / rowdel. 14 * Can also modify a corresponding solution to Lx=b when L is modified. This 15 * module is most useful when applied on a Cholesky factorization computed by 16 * the Cholesky module, but it does not actually require the Cholesky module. 17 * The Core module can create an identity Cholesky factorization (LDL' where 18 * L=D=I) that can then by modified by these routines. 19 * 20 * Primary routines: 21 * ----------------- 22 * 23 * cholmod_updown multiple rank update/downdate 24 * cholmod_rowadd add a row to an LDL' factorization 25 * cholmod_rowdel delete a row from an LDL' factorization 26 * 27 * Secondary routines: 28 * ------------------- 29 * 30 * cholmod_updown_solve update/downdate, and modify solution to Lx=b 31 * cholmod_updown_mark update/downdate, and modify solution to partial Lx=b 32 * cholmod_updown_mask update/downdate for LPDASA 33 * cholmod_updown_mask2 update/downdate for LPDASA 34 * cholmod_rowadd_solve add a row, and update solution to Lx=b 35 * cholmod_rowadd_mark add a row, and update solution to partial Lx=b 36 * cholmod_rowdel_solve delete a row, and downdate Lx=b 37 * cholmod_rowdel_mark delete a row, and downdate solution to partial Lx=b 38 * 39 * Requires the Core module. Not required by any other CHOLMOD module. 40 */ 41 42 #ifndef CHOLMOD_MODIFY_H 43 #define CHOLMOD_MODIFY_H 44 45 #include "cholmod_core.h" 46 47 /* -------------------------------------------------------------------------- */ 48 /* cholmod_updown: multiple rank update/downdate */ 49 /* -------------------------------------------------------------------------- */ 50 51 /* Compute the new LDL' factorization of LDL'+CC' (an update) or LDL'-CC' 52 * (a downdate). The factor object L need not be an LDL' factorization; it 53 * is converted to one if it isn't. */ 54 55 int cholmod_updown 56 ( 57 /* ---- input ---- */ 58 int update, /* TRUE for update, FALSE for downdate */ 59 cholmod_sparse *C, /* the incoming sparse update */ 60 /* ---- in/out --- */ 61 cholmod_factor *L, /* factor to modify */ 62 /* --------------- */ 63 cholmod_common *Common 64 ) ; 65 66 int cholmod_l_updown (int, cholmod_sparse *, cholmod_factor *, 67 cholmod_common *) ; 68 69 /* -------------------------------------------------------------------------- */ 70 /* cholmod_updown_solve: update/downdate, and modify solution to Lx=b */ 71 /* -------------------------------------------------------------------------- */ 72 73 /* Does the same as cholmod_updown, except that it also updates/downdates the 74 * solution to Lx=b+DeltaB. x and b must be n-by-1 dense matrices. b is not 75 * need as input to this routine, but a sparse change to b is (DeltaB). Only 76 * entries in DeltaB corresponding to columns modified in L are accessed; the 77 * rest must be zero. */ 78 79 int cholmod_updown_solve 80 ( 81 /* ---- input ---- */ 82 int update, /* TRUE for update, FALSE for downdate */ 83 cholmod_sparse *C, /* the incoming sparse update */ 84 /* ---- in/out --- */ 85 cholmod_factor *L, /* factor to modify */ 86 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 87 cholmod_dense *DeltaB, /* change in b, zero on output */ 88 /* --------------- */ 89 cholmod_common *Common 90 ) ; 91 92 int cholmod_l_updown_solve (int, cholmod_sparse *, cholmod_factor *, 93 cholmod_dense *, cholmod_dense *, cholmod_common *) ; 94 95 /* -------------------------------------------------------------------------- */ 96 /* cholmod_updown_mark: update/downdate, and modify solution to partial Lx=b */ 97 /* -------------------------------------------------------------------------- */ 98 99 /* Does the same as cholmod_updown_solve, except only part of L is used in 100 * the update/downdate of the solution to Lx=b. This routine is an "expert" 101 * routine. It is meant for use in LPDASA only. See cholmod_updown.c for 102 * a description of colmark. */ 103 104 int cholmod_updown_mark 105 ( 106 /* ---- input ---- */ 107 int update, /* TRUE for update, FALSE for downdate */ 108 cholmod_sparse *C, /* the incoming sparse update */ 109 int *colmark, /* int array of size n. See cholmod_updown.c */ 110 /* ---- in/out --- */ 111 cholmod_factor *L, /* factor to modify */ 112 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 113 cholmod_dense *DeltaB, /* change in b, zero on output */ 114 /* --------------- */ 115 cholmod_common *Common 116 ) ; 117 118 int cholmod_l_updown_mark (int, cholmod_sparse *, SuiteSparse_long *, 119 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 120 121 /* -------------------------------------------------------------------------- */ 122 /* cholmod_updown_mask: update/downdate, for LPDASA */ 123 /* -------------------------------------------------------------------------- */ 124 125 /* Does the same as cholmod_updown_mark, except has an additional "mask" 126 * argument. This routine is an "expert" routine. It is meant for use in 127 * LPDASA only. See cholmod_updown.c for a description of mask. */ 128 129 int cholmod_updown_mask 130 ( 131 /* ---- input ---- */ 132 int update, /* TRUE for update, FALSE for downdate */ 133 cholmod_sparse *C, /* the incoming sparse update */ 134 int *colmark, /* int array of size n. See cholmod_updown.c */ 135 int *mask, /* size n */ 136 /* ---- in/out --- */ 137 cholmod_factor *L, /* factor to modify */ 138 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 139 cholmod_dense *DeltaB, /* change in b, zero on output */ 140 /* --------------- */ 141 cholmod_common *Common 142 ) ; 143 144 int cholmod_l_updown_mask (int, cholmod_sparse *, SuiteSparse_long *, 145 SuiteSparse_long *, cholmod_factor *, cholmod_dense *, cholmod_dense *, 146 cholmod_common *) ; 147 148 int cholmod_updown_mask2 149 ( 150 /* ---- input ---- */ 151 int update, /* TRUE for update, FALSE for downdate */ 152 cholmod_sparse *C, /* the incoming sparse update */ 153 int *colmark, /* int array of size n. See cholmod_updown.c */ 154 int *mask, /* size n */ 155 int maskmark, 156 /* ---- in/out --- */ 157 cholmod_factor *L, /* factor to modify */ 158 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 159 cholmod_dense *DeltaB, /* change in b, zero on output */ 160 /* --------------- */ 161 cholmod_common *Common 162 ) ; 163 164 int cholmod_l_updown_mask2 (int, cholmod_sparse *, SuiteSparse_long *, 165 SuiteSparse_long *, SuiteSparse_long, cholmod_factor *, cholmod_dense *, 166 cholmod_dense *, cholmod_common *) ; 167 168 /* -------------------------------------------------------------------------- */ 169 /* cholmod_rowadd: add a row to an LDL' factorization (a rank-2 update) */ 170 /* -------------------------------------------------------------------------- */ 171 172 /* cholmod_rowadd adds a row to the LDL' factorization. It computes the kth 173 * row and kth column of L, and then updates the submatrix L (k+1:n,k+1:n) 174 * accordingly. The kth row and column of L must originally be equal to the 175 * kth row and column of the identity matrix. The kth row/column of L is 176 * computed as the factorization of the kth row/column of the matrix to 177 * factorize, which is provided as a single n-by-1 sparse matrix R. */ 178 179 int cholmod_rowadd 180 ( 181 /* ---- input ---- */ 182 size_t k, /* row/column index to add */ 183 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 184 /* ---- in/out --- */ 185 cholmod_factor *L, /* factor to modify */ 186 /* --------------- */ 187 cholmod_common *Common 188 ) ; 189 190 int cholmod_l_rowadd (size_t, cholmod_sparse *, cholmod_factor *, 191 cholmod_common *) ; 192 193 /* -------------------------------------------------------------------------- */ 194 /* cholmod_rowadd_solve: add a row, and update solution to Lx=b */ 195 /* -------------------------------------------------------------------------- */ 196 197 /* Does the same as cholmod_rowadd, and also updates the solution to Lx=b 198 * See cholmod_updown for a description of how Lx=b is updated. There is on 199 * additional parameter: bk specifies the new kth entry of b. */ 200 201 int cholmod_rowadd_solve 202 ( 203 /* ---- input ---- */ 204 size_t k, /* row/column index to add */ 205 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 206 double bk [2], /* kth entry of the right-hand-side b */ 207 /* ---- in/out --- */ 208 cholmod_factor *L, /* factor to modify */ 209 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 210 cholmod_dense *DeltaB, /* change in b, zero on output */ 211 /* --------------- */ 212 cholmod_common *Common 213 ) ; 214 215 int cholmod_l_rowadd_solve (size_t, cholmod_sparse *, double *, 216 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 217 218 /* -------------------------------------------------------------------------- */ 219 /* cholmod_rowadd_mark: add a row, and update solution to partial Lx=b */ 220 /* -------------------------------------------------------------------------- */ 221 222 /* Does the same as cholmod_rowadd_solve, except only part of L is used in 223 * the update/downdate of the solution to Lx=b. This routine is an "expert" 224 * routine. It is meant for use in LPDASA only. */ 225 226 int cholmod_rowadd_mark 227 ( 228 /* ---- input ---- */ 229 size_t k, /* row/column index to add */ 230 cholmod_sparse *R, /* row/column of matrix to factorize (n-by-1) */ 231 double bk [2], /* kth entry of the right hand side, b */ 232 int *colmark, /* int array of size n. See cholmod_updown.c */ 233 /* ---- in/out --- */ 234 cholmod_factor *L, /* factor to modify */ 235 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 236 cholmod_dense *DeltaB, /* change in b, zero on output */ 237 /* --------------- */ 238 cholmod_common *Common 239 ) ; 240 241 int cholmod_l_rowadd_mark (size_t, cholmod_sparse *, double *, 242 SuiteSparse_long *, cholmod_factor *, cholmod_dense *, cholmod_dense *, 243 cholmod_common *) ; 244 245 /* -------------------------------------------------------------------------- */ 246 /* cholmod_rowdel: delete a row from an LDL' factorization (a rank-2 update) */ 247 /* -------------------------------------------------------------------------- */ 248 249 /* Sets the kth row and column of L to be the kth row and column of the identity 250 * matrix, and updates L(k+1:n,k+1:n) accordingly. To reduce the running time, 251 * the caller can optionally provide the nonzero pattern (or an upper bound) of 252 * kth row of L, as the sparse n-by-1 vector R. Provide R as NULL if you want 253 * CHOLMOD to determine this itself, which is easier for the caller, but takes 254 * a little more time. 255 */ 256 257 int cholmod_rowdel 258 ( 259 /* ---- input ---- */ 260 size_t k, /* row/column index to delete */ 261 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 262 /* ---- in/out --- */ 263 cholmod_factor *L, /* factor to modify */ 264 /* --------------- */ 265 cholmod_common *Common 266 ) ; 267 268 int cholmod_l_rowdel (size_t, cholmod_sparse *, cholmod_factor *, 269 cholmod_common *) ; 270 271 /* -------------------------------------------------------------------------- */ 272 /* cholmod_rowdel_solve: delete a row, and downdate Lx=b */ 273 /* -------------------------------------------------------------------------- */ 274 275 /* Does the same as cholmod_rowdel, but also downdates the solution to Lx=b. 276 * When row/column k of A is "deleted" from the system A*y=b, this can induce 277 * a change to x, in addition to changes arising when L and b are modified. 278 * If this is the case, the kth entry of y is required as input (yk) */ 279 280 int cholmod_rowdel_solve 281 ( 282 /* ---- input ---- */ 283 size_t k, /* row/column index to delete */ 284 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 285 double yk [2], /* kth entry in the solution to A*y=b */ 286 /* ---- in/out --- */ 287 cholmod_factor *L, /* factor to modify */ 288 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 289 cholmod_dense *DeltaB, /* change in b, zero on output */ 290 /* --------------- */ 291 cholmod_common *Common 292 ) ; 293 294 int cholmod_l_rowdel_solve (size_t, cholmod_sparse *, double *, 295 cholmod_factor *, cholmod_dense *, cholmod_dense *, cholmod_common *) ; 296 297 /* -------------------------------------------------------------------------- */ 298 /* cholmod_rowdel_mark: delete a row, and downdate solution to partial Lx=b */ 299 /* -------------------------------------------------------------------------- */ 300 301 /* Does the same as cholmod_rowdel_solve, except only part of L is used in 302 * the update/downdate of the solution to Lx=b. This routine is an "expert" 303 * routine. It is meant for use in LPDASA only. */ 304 305 int cholmod_rowdel_mark 306 ( 307 /* ---- input ---- */ 308 size_t k, /* row/column index to delete */ 309 cholmod_sparse *R, /* NULL, or the nonzero pattern of kth row of L */ 310 double yk [2], /* kth entry in the solution to A*y=b */ 311 int *colmark, /* int array of size n. See cholmod_updown.c */ 312 /* ---- in/out --- */ 313 cholmod_factor *L, /* factor to modify */ 314 cholmod_dense *X, /* solution to Lx=b (size n-by-1) */ 315 cholmod_dense *DeltaB, /* change in b, zero on output */ 316 /* --------------- */ 317 cholmod_common *Common 318 ) ; 319 320 int cholmod_l_rowdel_mark (size_t, cholmod_sparse *, double *, 321 SuiteSparse_long *, cholmod_factor *, cholmod_dense *, cholmod_dense *, 322 cholmod_common *) ; 323 324 #endif 325