cholmod_cholesky.h
Go to the documentation of this file.00001 /* ========================================================================== */ 00002 /* === Include/cholmod_cholesky.h =========================================== */ 00003 /* ========================================================================== */ 00004 00005 /* ----------------------------------------------------------------------------- 00006 * CHOLMOD/Include/cholmod_cholesky.h. Copyright (C) 2005-2006, Timothy A. Davis 00007 * CHOLMOD/Include/cholmod_cholesky.h is licensed under Version 2.1 of the GNU 00008 * Lesser General Public License. See lesser.txt for a text of the license. 00009 * CHOLMOD is also available under other licenses; contact authors for details. 00010 * http://www.cise.ufl.edu/research/sparse 00011 * -------------------------------------------------------------------------- */ 00012 00013 /* CHOLMOD Cholesky module. 00014 * 00015 * Sparse Cholesky routines: analysis, factorization, and solve. 00016 * 00017 * The primary routines are all that a user requires to order, analyze, and 00018 * factorize a sparse symmetric positive definite matrix A (or A*A'), and 00019 * to solve Ax=b (or A*A'x=b). The primary routines rely on the secondary 00020 * routines, the CHOLMOD Core module, and the AMD and COLAMD packages. They 00021 * make optional use of the CHOLMOD Supernodal and Partition modules, the 00022 * METIS package, and the CCOLAMD package. 00023 * 00024 * Primary routines: 00025 * ----------------- 00026 * 00027 * cholmod_analyze order and analyze (simplicial or supernodal) 00028 * cholmod_factorize simplicial or supernodal Cholesky factorization 00029 * cholmod_solve solve a linear system (simplicial or supernodal) 00030 * cholmod_spsolve solve a linear system (sparse x and b) 00031 * 00032 * Secondary routines: 00033 * ------------------ 00034 * 00035 * cholmod_analyze_p analyze, with user-provided permutation or f set 00036 * cholmod_factorize_p factorize, with user-provided permutation or f 00037 * cholmod_analyze_ordering analyze a fill-reducing ordering 00038 * cholmod_etree find the elimination tree 00039 * cholmod_rowcolcounts compute the row/column counts of L 00040 * cholmod_amd order using AMD 00041 * cholmod_colamd order using COLAMD 00042 * cholmod_rowfac incremental simplicial factorization 00043 * cholmod_rowfac_mask rowfac, specific to LPDASA 00044 * cholmod_row_subtree find the nonzero pattern of a row of L 00045 * cholmod_resymbol recompute the symbolic pattern of L 00046 * cholmod_resymbol_noperm recompute the symbolic pattern of L, no L->Perm 00047 * cholmod_postorder postorder a tree 00048 * 00049 * Requires the Core module, and two packages: AMD and COLAMD. 00050 * Optionally uses the Supernodal and Partition modules. 00051 * Required by the Partition module. 00052 */ 00053 00054 #ifndef CHOLMOD_CHOLESKY_H 00055 #define CHOLMOD_CHOLESKY_H 00056 00057 #include "cholmod_config.h" 00058 #include "cholmod_core.h" 00059 00060 #ifndef NPARTITION 00061 #include "cholmod_partition.h" 00062 #endif 00063 00064 #ifndef NSUPERNODAL 00065 #include "cholmod_supernodal.h" 00066 #endif 00067 00068 /* -------------------------------------------------------------------------- */ 00069 /* cholmod_analyze: order and analyze (simplicial or supernodal) */ 00070 /* -------------------------------------------------------------------------- */ 00071 00072 /* Orders and analyzes A, AA', PAP', or PAA'P' and returns a symbolic factor 00073 * that can later be passed to cholmod_factorize. */ 00074 00075 cholmod_factor *cholmod_analyze 00076 ( 00077 /* ---- input ---- */ 00078 cholmod_sparse *A, /* matrix to order and analyze */ 00079 /* --------------- */ 00080 cholmod_common *Common 00081 ) ; 00082 00083 cholmod_factor *cholmod_l_analyze (cholmod_sparse *, cholmod_common *) ; 00084 00085 /* -------------------------------------------------------------------------- */ 00086 /* cholmod_analyze_p: analyze, with user-provided permutation or f set */ 00087 /* -------------------------------------------------------------------------- */ 00088 00089 /* Orders and analyzes A, AA', PAP', PAA'P', FF', or PFF'P and returns a 00090 * symbolic factor that can later be passed to cholmod_factorize, where 00091 * F = A(:,fset) if fset is not NULL and A->stype is zero. 00092 * UserPerm is tried if non-NULL. */ 00093 00094 cholmod_factor *cholmod_analyze_p 00095 ( 00096 /* ---- input ---- */ 00097 cholmod_sparse *A, /* matrix to order and analyze */ 00098 int *UserPerm, /* user-provided permutation, size A->nrow */ 00099 int *fset, /* subset of 0:(A->ncol)-1 */ 00100 size_t fsize, /* size of fset */ 00101 /* --------------- */ 00102 cholmod_common *Common 00103 ) ; 00104 00105 cholmod_factor *cholmod_l_analyze_p (cholmod_sparse *, UF_long *, UF_long *, 00106 size_t, cholmod_common *) ; 00107 00108 /* -------------------------------------------------------------------------- */ 00109 /* cholmod_analyze_p2: analyze for sparse Cholesky or sparse QR */ 00110 /* -------------------------------------------------------------------------- */ 00111 00112 cholmod_factor *cholmod_analyze_p2 00113 ( 00114 /* ---- input ---- */ 00115 int for_cholesky, /* if TRUE, then analyze for Cholesky; else for QR */ 00116 cholmod_sparse *A, /* matrix to order and analyze */ 00117 int *UserPerm, /* user-provided permutation, size A->nrow */ 00118 int *fset, /* subset of 0:(A->ncol)-1 */ 00119 size_t fsize, /* size of fset */ 00120 /* --------------- */ 00121 cholmod_common *Common 00122 ) ; 00123 00124 cholmod_factor *cholmod_l_analyze_p2 (int, cholmod_sparse *, UF_long *, 00125 UF_long *, size_t, cholmod_common *) ; 00126 00127 /* -------------------------------------------------------------------------- */ 00128 /* cholmod_factorize: simplicial or supernodal Cholesky factorization */ 00129 /* -------------------------------------------------------------------------- */ 00130 00131 /* Factorizes PAP' (or PAA'P' if A->stype is 0), using a factor obtained 00132 * from cholmod_analyze. The analysis can be re-used simply by calling this 00133 * routine a second time with another matrix. A must have the same nonzero 00134 * pattern as that passed to cholmod_analyze. */ 00135 00136 int cholmod_factorize 00137 ( 00138 /* ---- input ---- */ 00139 cholmod_sparse *A, /* matrix to factorize */ 00140 /* ---- in/out --- */ 00141 cholmod_factor *L, /* resulting factorization */ 00142 /* --------------- */ 00143 cholmod_common *Common 00144 ) ; 00145 00146 int cholmod_l_factorize (cholmod_sparse *, cholmod_factor *, cholmod_common *) ; 00147 00148 /* -------------------------------------------------------------------------- */ 00149 /* cholmod_factorize_p: factorize, with user-provided permutation or fset */ 00150 /* -------------------------------------------------------------------------- */ 00151 00152 /* Same as cholmod_factorize, but with more options. */ 00153 00154 int cholmod_factorize_p 00155 ( 00156 /* ---- input ---- */ 00157 cholmod_sparse *A, /* matrix to factorize */ 00158 double beta [2], /* factorize beta*I+A or beta*I+A'*A */ 00159 int *fset, /* subset of 0:(A->ncol)-1 */ 00160 size_t fsize, /* size of fset */ 00161 /* ---- in/out --- */ 00162 cholmod_factor *L, /* resulting factorization */ 00163 /* --------------- */ 00164 cholmod_common *Common 00165 ) ; 00166 00167 int cholmod_l_factorize_p (cholmod_sparse *, double *, UF_long *, size_t, 00168 cholmod_factor *, cholmod_common *) ; 00169 00170 /* -------------------------------------------------------------------------- */ 00171 /* cholmod_solve: solve a linear system (simplicial or supernodal) */ 00172 /* -------------------------------------------------------------------------- */ 00173 00174 /* Solves one of many linear systems with a dense right-hand-side, using the 00175 * factorization from cholmod_factorize (or as modified by any other CHOLMOD 00176 * routine). D is identity for LL' factorizations. */ 00177 00178 #define CHOLMOD_A 0 /* solve Ax=b */ 00179 #define CHOLMOD_LDLt 1 /* solve LDL'x=b */ 00180 #define CHOLMOD_LD 2 /* solve LDx=b */ 00181 #define CHOLMOD_DLt 3 /* solve DL'x=b */ 00182 #define CHOLMOD_L 4 /* solve Lx=b */ 00183 #define CHOLMOD_Lt 5 /* solve L'x=b */ 00184 #define CHOLMOD_D 6 /* solve Dx=b */ 00185 #define CHOLMOD_P 7 /* permute x=Px */ 00186 #define CHOLMOD_Pt 8 /* permute x=P'x */ 00187 00188 cholmod_dense *cholmod_solve /* returns the solution X */ 00189 ( 00190 /* ---- input ---- */ 00191 int sys, /* system to solve */ 00192 cholmod_factor *L, /* factorization to use */ 00193 cholmod_dense *B, /* right-hand-side */ 00194 /* --------------- */ 00195 cholmod_common *Common 00196 ) ; 00197 00198 cholmod_dense *cholmod_l_solve (int, cholmod_factor *, cholmod_dense *, 00199 cholmod_common *) ; 00200 00201 /* -------------------------------------------------------------------------- */ 00202 /* cholmod_spsolve: solve a linear system with a sparse right-hand-side */ 00203 /* -------------------------------------------------------------------------- */ 00204 00205 cholmod_sparse *cholmod_spsolve 00206 ( 00207 /* ---- input ---- */ 00208 int sys, /* system to solve */ 00209 cholmod_factor *L, /* factorization to use */ 00210 cholmod_sparse *B, /* right-hand-side */ 00211 /* --------------- */ 00212 cholmod_common *Common 00213 ) ; 00214 00215 cholmod_sparse *cholmod_l_spsolve (int, cholmod_factor *, cholmod_sparse *, 00216 cholmod_common *) ; 00217 00218 /* -------------------------------------------------------------------------- */ 00219 /* cholmod_etree: find the elimination tree of A or A'*A */ 00220 /* -------------------------------------------------------------------------- */ 00221 00222 int cholmod_etree 00223 ( 00224 /* ---- input ---- */ 00225 cholmod_sparse *A, 00226 /* ---- output --- */ 00227 int *Parent, /* size ncol. Parent [j] = p if p is the parent of j */ 00228 /* --------------- */ 00229 cholmod_common *Common 00230 ) ; 00231 00232 int cholmod_l_etree (cholmod_sparse *, UF_long *, cholmod_common *) ; 00233 00234 /* -------------------------------------------------------------------------- */ 00235 /* cholmod_rowcolcounts: compute the row/column counts of L */ 00236 /* -------------------------------------------------------------------------- */ 00237 00238 int cholmod_rowcolcounts 00239 ( 00240 /* ---- input ---- */ 00241 cholmod_sparse *A, /* matrix to analyze */ 00242 int *fset, /* subset of 0:(A->ncol)-1 */ 00243 size_t fsize, /* size of fset */ 00244 int *Parent, /* size nrow. Parent [i] = p if p is the parent of i */ 00245 int *Post, /* size nrow. Post [k] = i if i is the kth node in 00246 * the postordered etree. */ 00247 /* ---- output --- */ 00248 int *RowCount, /* size nrow. RowCount [i] = # entries in the ith row of 00249 * L, including the diagonal. */ 00250 int *ColCount, /* size nrow. ColCount [i] = # entries in the ith 00251 * column of L, including the diagonal. */ 00252 int *First, /* size nrow. First [i] = k is the least postordering 00253 * of any descendant of i. */ 00254 int *Level, /* size nrow. Level [i] is the length of the path from 00255 * i to the root, with Level [root] = 0. */ 00256 /* --------------- */ 00257 cholmod_common *Common 00258 ) ; 00259 00260 int cholmod_l_rowcolcounts (cholmod_sparse *, UF_long *, size_t, UF_long *, 00261 UF_long *, UF_long *, UF_long *, UF_long *, UF_long *, cholmod_common *) ; 00262 00263 /* -------------------------------------------------------------------------- */ 00264 /* cholmod_analyze_ordering: analyze a fill-reducing ordering */ 00265 /* -------------------------------------------------------------------------- */ 00266 00267 int cholmod_analyze_ordering 00268 ( 00269 /* ---- input ---- */ 00270 cholmod_sparse *A, /* matrix to analyze */ 00271 int ordering, /* ordering method used */ 00272 int *Perm, /* size n, fill-reducing permutation to analyze */ 00273 int *fset, /* subset of 0:(A->ncol)-1 */ 00274 size_t fsize, /* size of fset */ 00275 /* ---- output --- */ 00276 int *Parent, /* size n, elimination tree */ 00277 int *Post, /* size n, postordering of elimination tree */ 00278 int *ColCount, /* size n, nnz in each column of L */ 00279 /* ---- workspace */ 00280 int *First, /* size nworkspace for cholmod_postorder */ 00281 int *Level, /* size n workspace for cholmod_postorder */ 00282 /* --------------- */ 00283 cholmod_common *Common 00284 ) ; 00285 00286 int cholmod_l_analyze_ordering (cholmod_sparse *, int, UF_long *, UF_long *, 00287 size_t, UF_long *, UF_long *, UF_long *, UF_long *, UF_long *, 00288 cholmod_common *) ; 00289 00290 /* -------------------------------------------------------------------------- */ 00291 /* cholmod_amd: order using AMD */ 00292 /* -------------------------------------------------------------------------- */ 00293 00294 /* Finds a permutation P to reduce fill-in in the factorization of P*A*P' 00295 * or P*A*A'P' */ 00296 00297 int cholmod_amd 00298 ( 00299 /* ---- input ---- */ 00300 cholmod_sparse *A, /* matrix to order */ 00301 int *fset, /* subset of 0:(A->ncol)-1 */ 00302 size_t fsize, /* size of fset */ 00303 /* ---- output --- */ 00304 int *Perm, /* size A->nrow, output permutation */ 00305 /* --------------- */ 00306 cholmod_common *Common 00307 ) ; 00308 00309 int cholmod_l_amd (cholmod_sparse *, UF_long *, size_t, UF_long *, 00310 cholmod_common *) ; 00311 00312 /* -------------------------------------------------------------------------- */ 00313 /* cholmod_colamd: order using COLAMD */ 00314 /* -------------------------------------------------------------------------- */ 00315 00316 /* Finds a permutation P to reduce fill-in in the factorization of P*A*A'*P'. 00317 * Orders F*F' where F = A (:,fset) if fset is not NULL */ 00318 00319 int cholmod_colamd 00320 ( 00321 /* ---- input ---- */ 00322 cholmod_sparse *A, /* matrix to order */ 00323 int *fset, /* subset of 0:(A->ncol)-1 */ 00324 size_t fsize, /* size of fset */ 00325 int postorder, /* if TRUE, follow with a coletree postorder */ 00326 /* ---- output --- */ 00327 int *Perm, /* size A->nrow, output permutation */ 00328 /* --------------- */ 00329 cholmod_common *Common 00330 ) ; 00331 00332 int cholmod_l_colamd (cholmod_sparse *, UF_long *, size_t, int, UF_long *, 00333 cholmod_common *) ; 00334 00335 /* -------------------------------------------------------------------------- */ 00336 /* cholmod_rowfac: incremental simplicial factorization */ 00337 /* -------------------------------------------------------------------------- */ 00338 00339 /* Partial or complete simplicial factorization. Rows and columns kstart:kend-1 00340 * of L and D must be initially equal to rows/columns kstart:kend-1 of the 00341 * identity matrix. Row k can only be factorized if all descendants of node 00342 * k in the elimination tree have been factorized. */ 00343 00344 int cholmod_rowfac 00345 ( 00346 /* ---- input ---- */ 00347 cholmod_sparse *A, /* matrix to factorize */ 00348 cholmod_sparse *F, /* used for A*A' case only. F=A' or A(:,fset)' */ 00349 double beta [2], /* factorize beta*I+A or beta*I+A'*A */ 00350 size_t kstart, /* first row to factorize */ 00351 size_t kend, /* last row to factorize is kend-1 */ 00352 /* ---- in/out --- */ 00353 cholmod_factor *L, 00354 /* --------------- */ 00355 cholmod_common *Common 00356 ) ; 00357 00358 int cholmod_l_rowfac (cholmod_sparse *, cholmod_sparse *, double *, size_t, 00359 size_t, cholmod_factor *, cholmod_common *) ; 00360 00361 /* -------------------------------------------------------------------------- */ 00362 /* cholmod_rowfac_mask: incremental simplicial factorization */ 00363 /* -------------------------------------------------------------------------- */ 00364 00365 /* cholmod_rowfac_mask is a version of cholmod_rowfac that is specific to 00366 * LPDASA. It is unlikely to be needed by any other application. */ 00367 00368 int cholmod_rowfac_mask 00369 ( 00370 /* ---- input ---- */ 00371 cholmod_sparse *A, /* matrix to factorize */ 00372 cholmod_sparse *F, /* used for A*A' case only. F=A' or A(:,fset)' */ 00373 double beta [2], /* factorize beta*I+A or beta*I+A'*A */ 00374 size_t kstart, /* first row to factorize */ 00375 size_t kend, /* last row to factorize is kend-1 */ 00376 int *mask, /* if mask[i] >= 0, then set row i to zero */ 00377 int *RLinkUp, /* link list of rows to compute */ 00378 /* ---- in/out --- */ 00379 cholmod_factor *L, 00380 /* --------------- */ 00381 cholmod_common *Common 00382 ) ; 00383 00384 int cholmod_l_rowfac_mask (cholmod_sparse *, cholmod_sparse *, double *, size_t, 00385 size_t, UF_long *, UF_long *, cholmod_factor *, cholmod_common *) ; 00386 00387 /* -------------------------------------------------------------------------- */ 00388 /* cholmod_row_subtree: find the nonzero pattern of a row of L */ 00389 /* -------------------------------------------------------------------------- */ 00390 00391 /* Find the nonzero pattern of x for the system Lx=b where L = (0:k-1,0:k-1) 00392 * and b = kth column of A or A*A' (rows 0 to k-1 only) */ 00393 00394 int cholmod_row_subtree 00395 ( 00396 /* ---- input ---- */ 00397 cholmod_sparse *A, /* matrix to analyze */ 00398 cholmod_sparse *F, /* used for A*A' case only. F=A' or A(:,fset)' */ 00399 size_t k, /* row k of L */ 00400 int *Parent, /* elimination tree */ 00401 /* ---- output --- */ 00402 cholmod_sparse *R, /* pattern of L(k,:), 1-by-n with R->nzmax >= n */ 00403 /* --------------- */ 00404 cholmod_common *Common 00405 ) ; 00406 00407 int cholmod_l_row_subtree (cholmod_sparse *, cholmod_sparse *, size_t, 00408 UF_long *, cholmod_sparse *, cholmod_common *) ; 00409 00410 /* -------------------------------------------------------------------------- */ 00411 /* cholmod_row_lsubtree: find the nonzero pattern of a row of L */ 00412 /* -------------------------------------------------------------------------- */ 00413 00414 /* Identical to cholmod_row_subtree, except that it finds the elimination tree 00415 * from L itself. */ 00416 00417 int cholmod_row_lsubtree 00418 ( 00419 /* ---- input ---- */ 00420 cholmod_sparse *A, /* matrix to analyze */ 00421 int *Fi, size_t fnz, /* nonzero pattern of kth row of A', not required 00422 * for the symmetric case. Need not be sorted. */ 00423 size_t k, /* row k of L */ 00424 cholmod_factor *L, /* the factor L from which parent(i) is derived */ 00425 /* ---- output --- */ 00426 cholmod_sparse *R, /* pattern of L(k,:), 1-by-n with R->nzmax >= n */ 00427 /* --------------- */ 00428 cholmod_common *Common 00429 ) ; 00430 00431 int cholmod_l_row_lsubtree (cholmod_sparse *, UF_long *, size_t, 00432 size_t, cholmod_factor *, cholmod_sparse *, cholmod_common *) ; 00433 00434 /* -------------------------------------------------------------------------- */ 00435 /* cholmod_resymbol: recompute the symbolic pattern of L */ 00436 /* -------------------------------------------------------------------------- */ 00437 00438 /* Remove entries from L that are not in the factorization of P*A*P', P*A*A'*P', 00439 * or P*F*F'*P' (depending on A->stype and whether fset is NULL or not). 00440 * 00441 * cholmod_resymbol is the same as cholmod_resymbol_noperm, except that it 00442 * first permutes A according to L->Perm. A can be upper/lower/unsymmetric, 00443 * in contrast to cholmod_resymbol_noperm (which can be lower or unsym). */ 00444 00445 int cholmod_resymbol 00446 ( 00447 /* ---- input ---- */ 00448 cholmod_sparse *A, /* matrix to analyze */ 00449 int *fset, /* subset of 0:(A->ncol)-1 */ 00450 size_t fsize, /* size of fset */ 00451 int pack, /* if TRUE, pack the columns of L */ 00452 /* ---- in/out --- */ 00453 cholmod_factor *L, /* factorization, entries pruned on output */ 00454 /* --------------- */ 00455 cholmod_common *Common 00456 ) ; 00457 00458 int cholmod_l_resymbol (cholmod_sparse *, UF_long *, size_t, int, 00459 cholmod_factor *, cholmod_common *) ; 00460 00461 /* -------------------------------------------------------------------------- */ 00462 /* cholmod_resymbol_noperm: recompute the symbolic pattern of L, no L->Perm */ 00463 /* -------------------------------------------------------------------------- */ 00464 00465 /* Remove entries from L that are not in the factorization of A, A*A', 00466 * or F*F' (depending on A->stype and whether fset is NULL or not). */ 00467 00468 int cholmod_resymbol_noperm 00469 ( 00470 /* ---- input ---- */ 00471 cholmod_sparse *A, /* matrix to analyze */ 00472 int *fset, /* subset of 0:(A->ncol)-1 */ 00473 size_t fsize, /* size of fset */ 00474 int pack, /* if TRUE, pack the columns of L */ 00475 /* ---- in/out --- */ 00476 cholmod_factor *L, /* factorization, entries pruned on output */ 00477 /* --------------- */ 00478 cholmod_common *Common 00479 ) ; 00480 00481 int cholmod_l_resymbol_noperm (cholmod_sparse *, UF_long *, size_t, int, 00482 cholmod_factor *, cholmod_common *) ; 00483 00484 /* -------------------------------------------------------------------------- */ 00485 /* cholmod_rcond: compute rough estimate of reciprocal of condition number */ 00486 /* -------------------------------------------------------------------------- */ 00487 00488 double cholmod_rcond /* return min(diag(L)) / max(diag(L)) */ 00489 ( 00490 /* ---- input ---- */ 00491 cholmod_factor *L, 00492 /* --------------- */ 00493 cholmod_common *Common 00494 ) ; 00495 00496 double cholmod_l_rcond (cholmod_factor *, cholmod_common *) ; 00497 00498 /* -------------------------------------------------------------------------- */ 00499 /* cholmod_postorder: Compute the postorder of a tree */ 00500 /* -------------------------------------------------------------------------- */ 00501 00502 UF_long cholmod_postorder /* return # of nodes postordered */ 00503 ( 00504 /* ---- input ---- */ 00505 int *Parent, /* size n. Parent [j] = p if p is the parent of j */ 00506 size_t n, 00507 int *Weight_p, /* size n, optional. Weight [j] is weight of node j */ 00508 /* ---- output --- */ 00509 int *Post, /* size n. Post [k] = j is kth in postordered tree */ 00510 /* --------------- */ 00511 cholmod_common *Common 00512 ) ; 00513 00514 UF_long cholmod_l_postorder (UF_long *, size_t, UF_long *, UF_long *, 00515 cholmod_common *) ; 00516 00517 #endif