Multiple-rank modifications of a sparse Cholesky factorization Academic Article uri icon

abstract

  • Given a sparse symmetric positive definite matrix AAT and an associated sparse Cholesky factorization LDLT or LLT, we develop sparse techniques for updating the factorization after either adding a collection of columns to A or deleting a collection of columns from A. Our techniques are based on an analysis and manipulation of the underlying graph structure, using the framework developed in an earlier paper on rank-1 modifications [T. A. Davis and W. W. Hager, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606-627]. Computationally, the multiple-rank update has better memory traffic and executes much faster than an equivalent series of rank-1 updates since the multiple-rank update makes one pass through L computing the new entries, while a series of rank-1 updates requires multiple passes through L.

published proceedings

  • SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS

author list (cited authors)

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

complete list of authors

  • Davis, TA||Hager, WW