Amesos Package Browser (Single Doxygen Collection) Development
amesos_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 AMESOS_CHOLMOD_CHOLESKY_H
00055 #define AMESOS_CHOLMOD_CHOLESKY_H
00056 
00057 #include "amesos_cholmod_config.h"
00058 #include "amesos_cholmod_core.h"
00059   
00060 #ifndef NPARTITION
00061 #include "amesos_cholmod_partition.h"
00062 #endif
00063 
00064 /* -------------------------------------------------------------------------- */
00065 /* cholmod_analyze:  order and analyze (simplicial or supernodal) */
00066 /* -------------------------------------------------------------------------- */
00067 
00068 /* Orders and analyzes A, AA', PAP', or PAA'P' and returns a symbolic factor
00069  * that can later be passed to cholmod_factorize. */
00070 
00071 cholmod_factor *amesos_cholmod_analyze 
00072 (
00073     /* ---- input ---- */
00074     cholmod_sparse *A,  /* matrix to order and analyze */
00075     /* --------------- */
00076     cholmod_common *Common
00077 ) ;
00078 
00079 cholmod_factor *cholmod_l_analyze (cholmod_sparse *, cholmod_common *) ;
00080 
00081 /* -------------------------------------------------------------------------- */
00082 /* cholmod_analyze_p:  analyze, with user-provided permutation or f set */
00083 /* -------------------------------------------------------------------------- */
00084 
00085 /* Orders and analyzes A, AA', PAP', PAA'P', FF', or PFF'P and returns a
00086  * symbolic factor that can later be passed to cholmod_factorize, where
00087  * F = A(:,fset) if fset is not NULL and A->stype is zero.
00088  * UserPerm is tried if non-NULL.  */
00089 
00090 cholmod_factor *amesos_cholmod_analyze_p
00091 (
00092     /* ---- input ---- */
00093     cholmod_sparse *A,  /* matrix to order and analyze */
00094     int *UserPerm,  /* user-provided permutation, size A->nrow */
00095     int *fset,    /* subset of 0:(A->ncol)-1 */
00096     size_t fsize, /* size of fset */
00097     /* --------------- */
00098     cholmod_common *Common
00099 ) ;
00100 
00101 cholmod_factor *amesos_cholmod_l_analyze_p (cholmod_sparse *, UF_long *, UF_long *,
00102     size_t, cholmod_common *) ;
00103 
00104 /* -------------------------------------------------------------------------- */
00105 /* cholmod_factorize:  simplicial or supernodal Cholesky factorization */
00106 /* -------------------------------------------------------------------------- */
00107 
00108 /* Factorizes PAP' (or PAA'P' if A->stype is 0), using a factor obtained
00109  * from cholmod_analyze.  The analysis can be re-used simply by calling this
00110  * routine a second time with another matrix.  A must have the same nonzero
00111  * pattern as that passed to cholmod_analyze. */
00112 
00113 int amesos_cholmod_factorize 
00114 (
00115     /* ---- input ---- */
00116     cholmod_sparse *A,  /* matrix to factorize */
00117     /* ---- in/out --- */
00118     cholmod_factor *L,  /* resulting factorization */
00119     /* --------------- */
00120     cholmod_common *Common
00121 ) ;
00122 
00123 int amesos_cholmod_l_factorize (cholmod_sparse *, cholmod_factor *, cholmod_common *) ;
00124 
00125 /* -------------------------------------------------------------------------- */
00126 /* cholmod_factorize_p:  factorize, with user-provided permutation or fset */
00127 /* -------------------------------------------------------------------------- */
00128 
00129 /* Same as cholmod_factorize, but with more options. */
00130 
00131 int amesos_cholmod_factorize_p
00132 (
00133     /* ---- input ---- */
00134     cholmod_sparse *A,  /* matrix to factorize */
00135     double beta [2],  /* factorize beta*I+A or beta*I+A'*A */
00136     int *fset,    /* subset of 0:(A->ncol)-1 */
00137     size_t fsize, /* size of fset */
00138     /* ---- in/out --- */
00139     cholmod_factor *L,  /* resulting factorization */
00140     /* --------------- */
00141     cholmod_common *Common
00142 ) ;
00143 
00144 int amesos_cholmod_l_factorize_p (cholmod_sparse *, double *, UF_long *, size_t,
00145     cholmod_factor *, cholmod_common *) ;
00146 
00147 /* -------------------------------------------------------------------------- */
00148 /* cholmod_solve:  solve a linear system (simplicial or supernodal) */
00149 /* -------------------------------------------------------------------------- */
00150 
00151 /* Solves one of many linear systems with a dense right-hand-side, using the
00152  * factorization from cholmod_factorize (or as modified by any other CHOLMOD
00153  * routine).  D is identity for LL' factorizations. */
00154 
00155 #define CHOLMOD_A    0    /* solve Ax=b */
00156 #define CHOLMOD_LDLt 1    /* solve LDL'x=b */
00157 #define CHOLMOD_LD   2    /* solve LDx=b */
00158 #define CHOLMOD_DLt  3    /* solve DL'x=b */
00159 #define CHOLMOD_L    4    /* solve Lx=b */
00160 #define CHOLMOD_Lt   5    /* solve L'x=b */
00161 #define CHOLMOD_D    6    /* solve Dx=b */
00162 #define CHOLMOD_P    7    /* permute x=Px */
00163 #define CHOLMOD_Pt   8    /* permute x=P'x */
00164 
00165 cholmod_dense *amesos_cholmod_solve /* returns the solution X */
00166 (
00167     /* ---- input ---- */
00168     int sys,    /* system to solve */
00169     cholmod_factor *L,  /* factorization to use */
00170     cholmod_dense *B, /* right-hand-side */
00171     /* --------------- */
00172     cholmod_common *Common
00173 ) ;
00174 
00175 cholmod_dense *amesos_cholmod_l_solve (int, cholmod_factor *, cholmod_dense *,
00176     cholmod_common *) ;
00177 
00178 /* -------------------------------------------------------------------------- */
00179 /* cholmod_spsolve:  solve a linear system with a sparse right-hand-side */
00180 /* -------------------------------------------------------------------------- */
00181 
00182 cholmod_sparse *amesos_cholmod_spsolve
00183 (
00184     /* ---- input ---- */
00185     int sys,    /* system to solve */
00186     cholmod_factor *L,  /* factorization to use */
00187     cholmod_sparse *B,  /* right-hand-side */
00188     /* --------------- */
00189     cholmod_common *Common
00190 ) ;
00191 
00192 cholmod_sparse *amesos_cholmod_l_spsolve (int, cholmod_factor *, cholmod_sparse *,
00193     cholmod_common *) ;
00194 
00195 /* -------------------------------------------------------------------------- */
00196 /* cholmod_etree: find the elimination tree of A or A'*A */
00197 /* -------------------------------------------------------------------------- */
00198 
00199 int amesos_cholmod_etree
00200 (
00201     /* ---- input ---- */
00202     cholmod_sparse *A,
00203     /* ---- output --- */
00204     int *Parent,  /* size ncol.  Parent [j] = p if p is the parent of j */
00205     /* --------------- */
00206     cholmod_common *Common
00207 ) ;
00208 
00209 int amesos_cholmod_l_etree (cholmod_sparse *, UF_long *, cholmod_common *) ;
00210 
00211 /* -------------------------------------------------------------------------- */
00212 /* cholmod_rowcolcounts: compute the row/column counts of L */
00213 /* -------------------------------------------------------------------------- */
00214 
00215 int amesos_cholmod_rowcolcounts
00216 (
00217     /* ---- input ---- */
00218     cholmod_sparse *A,  /* matrix to analyze */
00219     int *fset,    /* subset of 0:(A->ncol)-1 */
00220     size_t fsize, /* size of fset */
00221     int *Parent,  /* size nrow.  Parent [i] = p if p is the parent of i */
00222     int *Post,    /* size nrow.  Post [k] = i if i is the kth node in
00223        * the postordered etree. */
00224     /* ---- output --- */
00225     int *RowCount,  /* size nrow. RowCount [i] = # entries in the ith row of
00226        * L, including the diagonal. */
00227     int *ColCount,  /* size nrow. ColCount [i] = # entries in the ith
00228        * column of L, including the diagonal. */
00229     int *First,   /* size nrow.  First [i] = k is the least postordering
00230        * of any descendant of i. */
00231     int *Level,   /* size nrow.  Level [i] is the length of the path from
00232        * i to the root, with Level [root] = 0. */
00233     /* --------------- */
00234     cholmod_common *Common
00235 ) ;
00236 
00237 int amesos_cholmod_l_rowcolcounts (cholmod_sparse *, UF_long *, size_t, UF_long *,
00238     UF_long *, UF_long *, UF_long *, UF_long *, UF_long *, cholmod_common *) ;
00239 
00240 /* -------------------------------------------------------------------------- */
00241 /* cholmod_analyze_ordering:  analyze a fill-reducing ordering */
00242 /* -------------------------------------------------------------------------- */
00243 
00244 int amesos_cholmod_analyze_ordering
00245 (
00246     /* ---- input ---- */
00247     cholmod_sparse *A,  /* matrix to analyze */
00248     int ordering, /* ordering method used */
00249     int *Perm,    /* size n, fill-reducing permutation to analyze */
00250     int *fset,    /* subset of 0:(A->ncol)-1 */
00251     size_t fsize, /* size of fset */
00252     /* ---- output --- */
00253     int *Parent,  /* size n, elimination tree */
00254     int *Post,    /* size n, postordering of elimination tree */
00255     int *ColCount,  /* size n, nnz in each column of L */
00256     /* ---- workspace  */
00257     int *First,   /* size nworkspace for cholmod_postorder */
00258     int *Level,   /* size n workspace for cholmod_postorder */
00259     /* --------------- */
00260     cholmod_common *Common
00261 ) ;
00262 
00263 int amesos_cholmod_l_analyze_ordering (cholmod_sparse *, int, UF_long *, UF_long *,
00264     size_t, UF_long *, UF_long *, UF_long *, UF_long *, UF_long *,
00265     cholmod_common *) ;
00266 
00267 /* -------------------------------------------------------------------------- */
00268 /* cholmod_amd:  order using AMD */
00269 /* -------------------------------------------------------------------------- */
00270 
00271 /* Finds a permutation P to reduce fill-in in the factorization of P*A*P'
00272  * or P*A*A'P' */
00273 
00274 int amesos_cholmod_amd
00275 (
00276     /* ---- input ---- */
00277     cholmod_sparse *A,  /* matrix to order */
00278     int *fset,    /* subset of 0:(A->ncol)-1 */
00279     size_t fsize, /* size of fset */
00280     /* ---- output --- */
00281     int *Perm,    /* size A->nrow, output permutation */
00282     /* --------------- */
00283     cholmod_common *Common
00284 ) ;
00285 
00286 int amesos_cholmod_l_amd (cholmod_sparse *, UF_long *, size_t, UF_long *,
00287     cholmod_common *) ;
00288 
00289 /* -------------------------------------------------------------------------- */
00290 /* cholmod_colamd:  order using COLAMD */
00291 /* -------------------------------------------------------------------------- */
00292 
00293 /* Finds a permutation P to reduce fill-in in the factorization of P*A*A'*P'.
00294  * Orders F*F' where F = A (:,fset) if fset is not NULL */
00295 
00296 int amesos_cholmod_colamd
00297 (
00298     /* ---- input ---- */
00299     cholmod_sparse *A,  /* matrix to order */
00300     int *fset,    /* subset of 0:(A->ncol)-1 */
00301     size_t fsize, /* size of fset */
00302     int postorder,  /* if TRUE, follow with a coletree postorder */
00303     /* ---- output --- */
00304     int *Perm,    /* size A->nrow, output permutation */
00305     /* --------------- */
00306     cholmod_common *Common
00307 ) ;
00308 
00309 int amesos_cholmod_l_colamd (cholmod_sparse *, UF_long *, size_t, int, UF_long *,
00310     cholmod_common *) ;
00311 
00312 /* -------------------------------------------------------------------------- */
00313 /* cholmod_rowfac:  incremental simplicial factorization */
00314 /* -------------------------------------------------------------------------- */
00315 
00316 /* Partial or complete simplicial factorization.  Rows and columns kstart:kend-1
00317  * of L and D must be initially equal to rows/columns kstart:kend-1 of the
00318  * identity matrix.   Row k can only be factorized if all descendants of node
00319  * k in the elimination tree have been factorized. */
00320 
00321 int amesos_cholmod_rowfac
00322 (
00323     /* ---- input ---- */
00324     cholmod_sparse *A,  /* matrix to factorize */
00325     cholmod_sparse *F,  /* used for A*A' case only. F=A' or A(:,fset)' */
00326     double beta [2],  /* factorize beta*I+A or beta*I+A'*A */
00327     size_t kstart,  /* first row to factorize */
00328     size_t kend,  /* last row to factorize is kend-1 */
00329     /* ---- in/out --- */
00330     cholmod_factor *L,
00331     /* --------------- */
00332     cholmod_common *Common
00333 ) ;
00334 
00335 int amesos_cholmod_l_rowfac (cholmod_sparse *, cholmod_sparse *, double *, size_t,
00336     size_t, cholmod_factor *, cholmod_common *) ;
00337 
00338 /* -------------------------------------------------------------------------- */
00339 /* cholmod_rowfac_mask:  incremental simplicial factorization */
00340 /* -------------------------------------------------------------------------- */
00341 
00342 /* cholmod_rowfac_mask is a version of cholmod_rowfac that is specific to
00343  * LPDASA.  It is unlikely to be needed by any other application. */
00344 
00345 int amesos_cholmod_rowfac_mask
00346 (
00347     /* ---- input ---- */
00348     cholmod_sparse *A,  /* matrix to factorize */
00349     cholmod_sparse *F,  /* used for A*A' case only. F=A' or A(:,fset)' */
00350     double beta [2],  /* factorize beta*I+A or beta*I+A'*A */
00351     size_t kstart,  /* first row to factorize */
00352     size_t kend,  /* last row to factorize is kend-1 */
00353     int *mask,    /* if mask[i] >= 0, then set row i to zero */
00354     int *RLinkUp, /* link list of rows to compute */
00355     /* ---- in/out --- */
00356     cholmod_factor *L,
00357     /* --------------- */
00358     cholmod_common *Common
00359 ) ;
00360 
00361 int amesos_cholmod_l_rowfac_mask (cholmod_sparse *, cholmod_sparse *, double *, size_t,
00362     size_t, UF_long *, UF_long *, cholmod_factor *, cholmod_common *) ;
00363 
00364 /* -------------------------------------------------------------------------- */
00365 /* cholmod_row_subtree:  find the nonzero pattern of a row of L */
00366 /* -------------------------------------------------------------------------- */
00367 
00368 /* Find the nonzero pattern of x for the system Lx=b where L = (0:k-1,0:k-1)
00369  * and b = kth column of A or A*A' (rows 0 to k-1 only) */
00370 
00371 int amesos_cholmod_row_subtree
00372 (
00373     /* ---- input ---- */
00374     cholmod_sparse *A,  /* matrix to analyze */
00375     cholmod_sparse *F,  /* used for A*A' case only. F=A' or A(:,fset)' */
00376     size_t k,   /* row k of L */
00377     int *Parent,  /* elimination tree */
00378     /* ---- output --- */
00379     cholmod_sparse *R,  /* pattern of L(k,:), 1-by-n with R->nzmax >= n */
00380     /* --------------- */
00381     cholmod_common *Common
00382 ) ;
00383 
00384 int amesos_cholmod_l_row_subtree (cholmod_sparse *, cholmod_sparse *, size_t,
00385     UF_long *, cholmod_sparse *, cholmod_common *) ;
00386 
00387 /* -------------------------------------------------------------------------- */
00388 /* cholmod_row_lsubtree:  find the nonzero pattern of a row of L */
00389 /* -------------------------------------------------------------------------- */
00390 
00391 /* Identical to cholmod_row_subtree, except that it finds the elimination tree
00392  * from L itself. */
00393 
00394 int amesos_cholmod_row_lsubtree
00395 (
00396     /* ---- input ---- */
00397     cholmod_sparse *A,  /* matrix to analyze */
00398     int *Fi, size_t fnz,    /* nonzero pattern of kth row of A', not required
00399            * for the symmetric case.  Need not be sorted. */
00400     size_t k,   /* row k of L */
00401     cholmod_factor *L,  /* the factor L from which parent(i) is derived */
00402     /* ---- output --- */
00403     cholmod_sparse *R,  /* pattern of L(k,:), 1-by-n with R->nzmax >= n */
00404     /* --------------- */
00405     cholmod_common *Common
00406 ) ;
00407 
00408 int amesos_cholmod_l_row_lsubtree (cholmod_sparse *, UF_long *, size_t,
00409     size_t, cholmod_factor *, cholmod_sparse *, cholmod_common *) ;
00410 
00411 /* -------------------------------------------------------------------------- */
00412 /* cholmod_resymbol:  recompute the symbolic pattern of L */
00413 /* -------------------------------------------------------------------------- */
00414 
00415 /* Remove entries from L that are not in the factorization of P*A*P', P*A*A'*P',
00416  * or P*F*F'*P' (depending on A->stype and whether fset is NULL or not).
00417  *
00418  * cholmod_resymbol is the same as cholmod_resymbol_noperm, except that it
00419  * first permutes A according to L->Perm.  A can be upper/lower/unsymmetric,
00420  * in contrast to cholmod_resymbol_noperm (which can be lower or unsym). */
00421 
00422 int amesos_cholmod_resymbol 
00423 (
00424     /* ---- input ---- */
00425     cholmod_sparse *A,  /* matrix to analyze */
00426     int *fset,    /* subset of 0:(A->ncol)-1 */
00427     size_t fsize, /* size of fset */
00428     int pack,   /* if TRUE, pack the columns of L */
00429     /* ---- in/out --- */
00430     cholmod_factor *L,  /* factorization, entries pruned on output */
00431     /* --------------- */
00432     cholmod_common *Common
00433 ) ;
00434 
00435 int amesos_cholmod_l_resymbol (cholmod_sparse *, UF_long *, size_t, int,
00436     cholmod_factor *, cholmod_common *) ;
00437 
00438 /* -------------------------------------------------------------------------- */
00439 /* cholmod_resymbol_noperm:  recompute the symbolic pattern of L, no L->Perm */
00440 /* -------------------------------------------------------------------------- */
00441 
00442 /* Remove entries from L that are not in the factorization of A, A*A',
00443  * or F*F' (depending on A->stype and whether fset is NULL or not). */
00444 
00445 int amesos_cholmod_resymbol_noperm
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 amesos_cholmod_l_resymbol_noperm (cholmod_sparse *, UF_long *, size_t, int,
00459     cholmod_factor *, cholmod_common *) ;
00460 
00461 /* -------------------------------------------------------------------------- */
00462 /* cholmod_rcond:  compute rough estimate of reciprocal of condition number */
00463 /* -------------------------------------------------------------------------- */
00464 
00465 double amesos_cholmod_rcond     /* return min(diag(L)) / max(diag(L)) */
00466 (
00467     /* ---- input ---- */
00468     cholmod_factor *L,
00469     /* --------------- */
00470     cholmod_common *Common
00471 ) ;
00472 
00473 double amesos_cholmod_l_rcond (cholmod_factor *, cholmod_common *) ;
00474 
00475 /* -------------------------------------------------------------------------- */
00476 /* cholmod_postorder: Compute the postorder of a tree */
00477 /* -------------------------------------------------------------------------- */
00478 
00479 UF_long amesos_cholmod_postorder  /* return # of nodes postordered */
00480 (
00481     /* ---- input ---- */
00482     int *Parent,  /* size n. Parent [j] = p if p is the parent of j */
00483     size_t n,
00484     int *Weight_p,  /* size n, optional. Weight [j] is weight of node j */
00485     /* ---- output --- */
00486     int *Post,    /* size n. Post [k] = j is kth in postordered tree */
00487     /* --------------- */
00488     cholmod_common *Common
00489 ) ;
00490 
00491 UF_long amesos_cholmod_l_postorder (UF_long *, size_t, UF_long *, UF_long *,
00492     cholmod_common *) ;
00493 
00494 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines