An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices

Yuanzhe Xi; Ruipeng Li; Yousef Saad

doi:10.1137/15M1021830

An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices

Yuanzhe Xi, Ruipeng Li, Yousef Saad

Computer Science and Engineering

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

27 Scopus citations

Abstract

This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This "Multilevel Schur Low-Rank" (MSLR) preconditioner first builds a tree structure T based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of T and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.

Original language	English (US)
Pages (from-to)	235-259
Number of pages	25
Journal	SIAM Journal on Matrix Analysis and Applications
Volume	37
Issue number	1
DOIs	https://doi.org/10.1137/15M1021830
State	Published - 2016

Bibliographical note

Funding Information:
Received by the editors May 18, 2015; accepted for publication (in revised form) by L. Giraud December 10, 2015; published electronically March 3, 2016. This work was supported by the NSF under grants DMS-1216366 and DMS-1521573 and by the Minnesota Supercomputing Institute. 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/37-1/M102183.html †Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455-0154 (yxi@cs.umn.edu, saad@cs.umn.edu). ‡Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94551 (li50@llnl.gov). This authoŕs work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344 (LLNL-JRNL-680317).

Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Keywords

Domain decomposition
Incomplete factorization
Krylov subspace methods
Low-rank approximation
Multilevel preconditioner
Nested Dissection ordering
Schur complements

Publisher link

10.1137/15M1021830

Find It

Find It at U of M Libraries

Cite this

@article{20432778f76443b695b610cd53cbe2f0,

title = "An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices",

abstract = "This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This {"}Multilevel Schur Low-Rank{"} (MSLR) preconditioner first builds a tree structure T based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of T and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.",

keywords = "Domain decomposition, Incomplete factorization, Krylov subspace methods, Low-rank approximation, Multilevel preconditioner, Nested Dissection ordering, Schur complements",

author = "Yuanzhe Xi and Ruipeng Li and Yousef Saad",

note = "Funding Information: Received by the editors May 18, 2015; accepted for publication (in revised form) by L. Giraud December 10, 2015; published electronically March 3, 2016. This work was supported by the NSF under grants DMS-1216366 and DMS-1521573 and by the Minnesota Supercomputing Institute. 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/37-1/M102183.html †Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455-0154 (yxi@cs.umn.edu, saad@cs.umn.edu). ‡Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94551 (li50@llnl.gov). This autho{\'r}s work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344 (LLNL-JRNL-680317). Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2016",

doi = "10.1137/15M1021830",

language = "English (US)",

volume = "37",

pages = "235--259",

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

issn = "0895-4798",

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

number = "1",

}

TY - JOUR

T1 - An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices

AU - Xi, Yuanzhe

AU - Li, Ruipeng

AU - Saad, Yousef

N1 - Funding Information: Received by the editors May 18, 2015; accepted for publication (in revised form) by L. Giraud December 10, 2015; published electronically March 3, 2016. This work was supported by the NSF under grants DMS-1216366 and DMS-1521573 and by the Minnesota Supercomputing Institute. 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/37-1/M102183.html †Department of Computer Science and Engineering, University of Minnesota, Minneapolis, MN 55455-0154 (yxi@cs.umn.edu, saad@cs.umn.edu). ‡Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94551 (li50@llnl.gov). This authoŕs work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract DE-AC52-07NA27344 (LLNL-JRNL-680317). Publisher Copyright: Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2016

Y1 - 2016

N2 - This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This "Multilevel Schur Low-Rank" (MSLR) preconditioner first builds a tree structure T based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of T and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.

AB - This paper describes a multilevel preconditioning technique for solving sparse symmetric linear systems of equations. This "Multilevel Schur Low-Rank" (MSLR) preconditioner first builds a tree structure T based on a hierarchical decomposition of the matrix and then computes an approximate inverse of the original matrix level by level. Unlike classical direct solvers, the construction of the MSLR preconditioner follows a top-down traversal of T and exploits a low-rank property that is satisfied by the difference between the inverses of the local Schur complements and specific blocks of the original matrix. A few steps of the generalized Lanczos tridiagonalization procedure are applied to capture most of this difference. Numerical results are reported to illustrate the efficiency and robustness of the MSLR preconditioner with both two- and three-dimensional discretized PDE problems and with publicly available test problems.

KW - Domain decomposition

KW - Incomplete factorization

KW - Krylov subspace methods

KW - Low-rank approximation

KW - Multilevel preconditioner

KW - Nested Dissection ordering

KW - Schur complements

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

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

U2 - 10.1137/15M1021830

DO - 10.1137/15M1021830

M3 - Article

AN - SCOPUS:84962146879

VL - 37

SP - 235

EP - 259

JO - SIAM Journal on Matrix Analysis and Applications

JF - SIAM Journal on Matrix Analysis and Applications

SN - 0895-4798

IS - 1

ER -

An algebraic multilevel preconditioner with low-rank corrections for sparse symmetric matrices

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this