Multiple-Rank Modifications of a Sparse Cholesky Factorization
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 22 (4), 997-1013
- https://doi.org/10.1137/s0895479899357346
Abstract
Given a sparse symmetric positive definite matrix $\mathbf{AA}\tr$ and an associated sparse Cholesky factorization $\mathbf{LDL}\tr$ or $\mathbf{LL}\tr$, 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.
Keywords
This publication has 14 references indexed in Scilit:
- Modifying a Sparse Cholesky FactorizationSIAM Journal on Matrix Analysis and Applications, 1999
- An Approximate Minimum Degree Ordering AlgorithmSIAM Journal on Matrix Analysis and Applications, 1996
- A Cholesky Up- and Downdating Algorithm for Systolic and SIMD ArchitecturesSIAM Journal on Scientific Computing, 1993
- Sparse Matrices in MATLAB: Design and ImplementationSIAM Journal on Matrix Analysis and Applications, 1992
- A set of level 3 basic linear algebra subprogramsACM Transactions on Mathematical Software, 1990
- Vectorization of a Multiprocessor Multifrontal CodeThe International Journal of Supercomputing Applications, 1989
- A Data Structure for Sparse $QR$ and $LU$ FactorizationsSIAM Journal on Scientific and Statistical Computing, 1988
- Distribution of mathematical software via electronic mailCommunications of the ACM, 1987
- The Multifrontal Solution of Indefinite Sparse Symmetric LinearACM Transactions on Mathematical Software, 1983
- Methods for modifying matrix factorizationsMathematics of Computation, 1974