Modifying a sparse Cholesky factorization

Citation
Ta. Davis et Ww. Hager, Modifying a sparse Cholesky factorization, SIAM J MATR, 20(3), 1999, pp. 606-627
Citations number
35
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
ISSN journal
08954798 → ACNP
Volume
20
Issue
3
Year of publication
1999
Pages
606 - 627
Database
ISI
SICI code
0895-4798(19990713)20:3<606:MASCF>2.0.ZU;2-8
Abstract
Given a sparse symmetric positive definite matrix AA(T) and an associated s parse 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 m anipulation of the underlying graph structure and on ideas of Gill et al. [ Math. Comp., 28 (1974), pp. 505-535] for modifying a dense Cholesky factori zation. We show that our methods extend to the general case where an arbitr ary sparse symmetric positive definite matrix is modified. Our methods are optimal in the sense that they take time proportional to the number of nonz ero entries in L and D that change.