Dynamic Supernodes in Sparse Cholesky Update/Downdate and Triangular Solves Academic Article uri icon

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 WW 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 MATLAB when A is sparse and symmetric positive definite.

published proceedings

  • ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

author list (cited authors)

  • Davis, T. A., & Hager, W. W.

complete list of authors

  • Davis, Timothy A||Hager, William W

publication date

  • January 1, 2009 11:11 AM