Low-rank correction methods for algebraic domain decomposition preconditioners

Ruipeng Li; Yousef Saad

doi:10.1137/16M110486X

Low-rank correction methods for algebraic domain decomposition preconditioners

Ruipeng Li, Yousef Saad

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

13 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 language	English (US)
Pages (from-to)	807-828
Number of pages	22
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	38
Issue number	3
DOIs	https://doi.org/10.1137/16M110486X
State	Published - 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.

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

Keywords

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

Access

10.1137/16M110486X

Cite this

@article{3ac8f96ff8f94cf8b4a8b4fb8c281d73,

title = "Low-rank correction methods for algebraic domain decomposition preconditioners",

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{\textquoteright}s equation and linear elasticity problems.",

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

author = "Ruipeng Li and Yousef Saad",

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: {\textcopyright} 2017 Society for Industrial and Applied Mathematics.",

year = "2017",

doi = "10.1137/16M110486X",

language = "English (US)",

volume = "38",

pages = "807--828",

journal = "SIAM Journal on Matrix Analysis and Applications",

issn = "0895-4798",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Low-rank correction methods for algebraic domain decomposition preconditioners

AU - Li, Ruipeng

AU - Saad, Yousef

N1 - 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.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Distributed sparse linear systems

KW - Domain decomposition

KW - Incomplete LU factorization

KW - Krylov subspace method

KW - Low-rank approximation

KW - Parallel preconditioner

KW - Sherman–Morrison–Woodbury formula

UR - http://www.scopus.com/inward/record.url?scp=85031793350&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85031793350&partnerID=8YFLogxK

U2 - 10.1137/16M110486X

DO - 10.1137/16M110486X

M3 - Article

AN - SCOPUS:85031793350

VL - 38

SP - 807

EP - 828

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 3

ER -

Low-rank correction methods for algebraic domain decomposition preconditioners

Abstract

Bibliographical note

Keywords

Access

Other files and links

Fingerprint

Cite this