DIVIDE AND CONQUER LOW-RANK PRECONDITIONERS FOR SYMMETRIC MATRICES

作者：Li Ruipeng^*; Saad Yousef

来源：SIAM Journal on Scientific Computing, 2013, 35(4): A2069-A2095.

DOI：10.1137/120872735

• Sherman-Morrison formula
• low-rank approximation
• singular value decomposition
• recursive multilevel preconditioner
• parallel preconditioner
• incomplete LU factorization
• Krylov subspace method
• domain decomposition

This paper presents a preconditioning method based on an approximate inverse of the original matrix, computed recursively from a multilevel low-rank (MLR) expansion approach. The basic idea is to recursively divide the problem in two and apply a low-rank approximation to a matrix obtained from the Sherman-Morrison formula. The low-rank expansion is computed by a few steps of the Lanczos bidiagonalization procedure. The MLR preconditioner has been motivated by its potential for exploiting different levels of parallelism on modern high-performance platforms, though this feature is not yet tested in this paper. Numerical experiments indicate that, when combined with Krylov subspace accelerators, this preconditioner can be efficient and robust for solving symmetric sparse linear systems.

• 出版日期2013