Dynamic supernodes in sparse Cholesky update/downdate and triangular solves

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, [bar.A] = A [+ or -] [WW.sup.T]). 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 in MATLAB when A is sparse and symmetric positive definite. Categories and Subject Descriptors: G.1.3 [Numerical Analysis]: Numerical Linear Algebra-Linear systems (direct methods); sparse and very large systems; G.4 [Mathematics of Computing]: Mathematical Software---Algorithm analysis; efficiency General Terms: Algorithms, Experimentation, Performance Additional Key Words and Phrases: Cholesky factorization, linear equations, sparse matrices DOI = 10.1145/1462173.1462176.