Row Modifications of a Sparse Cholesky Factorization
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 26 (3) , 621-639
- https://doi.org/10.1137/s089547980343641x
Abstract
Given a sparse, symmetric positive definite matrix C and an associated sparse Cholesky factorization LDL$\tr$, we develop sparse techniques for updating the factorization after a symmetric modification of a row and column of C. We show how the modification in the Cholesky factorization associated with this rank-2 modification of C can be computed efficiently using a sparse rank-1 technique developed in [T. A. Davis and W. W. Hager, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 606--627]. We also determine how the solution of a linear system Lx = b changes after changing a row and column of C or after a rank-r change in C.Keywords
This publication has 14 references indexed in Scilit:
- Multiple-Rank Modifications of a Sparse Cholesky FactorizationSIAM Journal on Matrix Analysis and Applications, 2001
- Predicting Structure in Sparse Matrix ComputationsSIAM Journal on Matrix Analysis and Applications, 1994
- The Role of Elimination Trees in Sparse FactorizationSIAM Journal on Matrix Analysis and Applications, 1990
- Updating the Inverse of a MatrixSIAM Review, 1989
- Sparse Partial Pivoting in Time Proportional to Arithmetic OperationsSIAM Journal on Scientific and Statistical Computing, 1988
- A compact row storage scheme for Cholesky factors using elimination treesACM Transactions on Mathematical Software, 1986
- A New Implementation of Sparse Gaussian EliminationACM Transactions on Mathematical Software, 1982
- Yale sparse matrix package I: The symmetric codesInternational Journal for Numerical Methods in Engineering, 1982
- An Optimal Agorithm for Symbolic Factorization of Symmetric MatricesSIAM Journal on Computing, 1980
- Methods for modifying matrix factorizationsMathematics of Computation, 1974