Low-rank correction methods for algebraic domain decomposition preconditioners

Ruipeng Li, Yousef Saad

Research output: Contribution to journalArticlepeer-review

15 Scopus citations

Abstract

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
Volume38
Issue number3
DOIs
StatePublished - 2017

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.

Keywords

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

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

Cite this