Low-rank correction methods for algebraic domain decomposition preconditioners

Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


This paper presents a parallel preconditioning method for distributed sparse linear systems, based on an approximate inverse of the original matrix, that adopts a general framework of distributed sparse matrices and exploits domain decomposition (DD) and low-rank corrections. The DD approach decouples the matrix and, once inverted, a low-rank approximation is applied by exploiting the Sherman–Morrison–Woodbury formula, which yields two variants of the preconditioning methods. The low-rank expansion is computed by the Lanczos procedure with reorthogonalizations. Numerical experiments indicate that, when combined with Krylov subspace accelerators, this preconditioner can be efficient and robust for solving symmetric sparse linear systems. Comparisons with pARMS, a DD-based parallel incomplete LU (ILU) preconditioning method, are presented for solving Poisson’s equation and linear elasticity problems.

Original languageEnglish (US)
Pages (from-to)807-828
Number of pages22
JournalSIAM Journal on Matrix Analysis and Applications
Issue number3
StatePublished - 2017
Externally publishedYes

Bibliographical note

Funding Information:
∗Received by the editors November 23, 2016; accepted for publication (in revised form) by L. Giraud April 19, 2017; published electronically August 1, 2017. The U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes. Copyright is owned by SIAM to the extent not limited by these rights. http://www.siam.org/journals/simax/38-3/M110486.html Funding: The work of the first author was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344 (LLNL-JRNL-727122). The work of the second author was supported by the NSF under grants NSF/DMS-1216366 and NSF/DMS-1521573.

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.


  • Distributed sparse linear systems
  • Domain decomposition
  • Incomplete LU factorization
  • Krylov subspace method
  • Low-rank approximation
  • Parallel preconditioner
  • Sherman–Morrison–Woodbury formula


Dive into the research topics of 'Low-rank correction methods for algebraic domain decomposition preconditioners'. Together they form a unique fingerprint.

Cite this