Modifying 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 obtaining the new factorization associated with either adding a column to A or deleting a column from A. Our techniques are based on an analysis and manipulation of the underlying graph structure and on ideas of Gill et al. [Math. Comp., 28 (1974), pp. 505-535] for modifying a dense Cholesky factorization. We show that our methods extend to the general case where an arbitrary sparse symmetric positive definite matrix is modified. Our methods are optimal in the sense that they take time proportional to the number of nonzero entries in L and D that change.

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