Name
Abstract | ||
|---|---|---|
The supernodal method for sparse Cholesky factorization represents the factor L as a set of supernodes, each consisting of a contiguous set of columns of L with identical nonzero pattern. A conventional supernode is stored as a dense submatrix. While this is suitable for sparse Cholesky factorization where the nonzero pattern of L does not change, it is not suitable for methods that modify a sparse Cholesky factorization after a low-rank change to A (an update/downdate, Ā = A ± WWT). Supernodes merge and split apart during an update/downdate. Dynamic supernodes are introduced which allow a sparse Cholesky update/downdate to obtain performance competitive with conventional supernodal methods. A dynamic supernodal solver is shown to exceed the performance of the conventional (BLAS-based) supernodal method for solving triangular systems. These methods are incorporated into CHOLMOD, a sparse Cholesky factorization and update/downdate package which forms the basis of x = A\b MATLAB when A is sparse and symmetric positive definite. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1462173.1462176 | ACM Trans. Math. Softw. |
Keywords | Field | DocType |
conventional supernodal method,factor l,sparse matrices,sparse cholesky update,sparse cholesky factorization,linear equations,dynamic supernodes,triangular solves,dynamic supernodal solver,downdate package,conventional supernode,supernodal method,contiguous set,cholesky factorization,algorithms | Incomplete Cholesky factorization,Positive-definite matrix,Matrix decomposition,Minimum degree algorithm,Algorithm,Solver,Supernode,Sparse matrix,Mathematics,Cholesky decomposition | Journal |
Volume | Issue | ISSN |
35 | 4 | 0098-3500 |
Citations | PageRank | References |
28 | 2.12 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| TIMOTHY A. DAVIS | 1 | 1447 | 144.19 |
| William W. Hager | 2 | 1603 | 214.67 |