Multiple-rank modifications of a sparse Cholesky factorization

Citation
Ta. Davis et Ww. Hager, Multiple-rank modifications of a sparse Cholesky factorization, SIAM J MATR, 22(4), 2001, pp. 997-1013
Citations number
26
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
ISSN journal
08954798 → ACNP
Volume
22
Issue
4
Year of publication
2001
Pages
997 - 1013
Database
ISI
SICI code
0895-4798(20010412)22:4<997:MMOASC>2.0.ZU;2-B
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 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 fra mework developed in an earlier paper on rank-1 modi cations [ T. A. Davis a nd W. W. Hager, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606-627]. Comput ationally, 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 ser ies of rank-1 updates requires multiple passes through L.