Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
Authors:
- Jianlin XiaJXJianlin Xia
- Ming GuMGMing Gu
- 1 January 2010
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 31 (5) , 2899-2920
Abstract
Given a symmetric positive definite matrix A, we compute a structured approximate Cholesky factorization $A\approx\mathbf{R}^{T}\mathbf{R}$ up to any desired accuracy, where $\mathbf{R}$ is an upper triangular hierarchically semiseparable (HSS) matrix. The factorization is stable, robust, and efficient. The method compresses off-diagonal blocks with rank-revealing orthogonal decompositions. In the meantime, positive semidefinite terms are automatically and implicitly added to Schur complements in the factorization so that the approximation $\mathbf{R}^{T}\mathbf{R}$ is guaranteed to exist and be positive definite. The approximate factorization can be used as a structured preconditioner which does not break down. No extra stabilization step is needed. When A has an off-diagonal low-rank property, or when the off-diagonal blocks of A have small numerical ranks, the preconditioner is data sparse and is especially efficient. Furthermore, the method has a good potential to give satisfactory preconditioning bou...
Keywords
This publication has 47 references indexed in Scilit:
- Parallel black box $\mathcal {H}$ -LU preconditioning for elliptic boundary value problemsComputing and Visualization in Science, 2008
- Stabilized rounded addition of hierarchical matricesNumerical Linear Algebra with Applications, 2007
- -Matrix Arithmetics in Linear ComplexityComputing, 2005
- A bibliography on semiseparable matrices*Calcolo, 2005
- Orthogonal similarity transformation into block-semiseparable matrices of semiseparability rankkNumerical Linear Algebra with Applications, 2005
- Hierarchical Matrices Based on a Weak Admissibility CriterionComputing, 2004
- Introduction to hierarchical matrices with applicationsEngineering Analysis with Boundary Elements, 2003
- AMLI preconditioner for thep-version of the FEMNumerical Linear Algebra with Applications, 2003
- Incomplete Cross Approximation in the Mosaic-Skeleton MethodComputing, 2000
- Semi On-Line Scheduling on Two Identical MachinesComputing, 1999