Schur complement-based domain decomposition preconditioners with low-rank corrections

Ruipeng Li, Yuanzhe XI, Yousef Saad

Research output: Contribution to journalArticle

9 Citations (Scopus)

Abstract

This paper introduces a robust preconditioner for general sparse matrices based on low-rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low-rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach.

Original languageEnglish (US)
Pages (from-to)706-729
Number of pages24
JournalNumerical Linear Algebra with Applications
Volume23
Issue number4
DOIs
StatePublished - Aug 1 2016

Fingerprint

Schur Complement
Domain Decomposition
Preconditioner
Spectrum analysis
Decomposition
Experiments
Nonsymmetric Matrix
Low-rank Approximation
Approximate Inverse
Symmetric Positive Definite Matrix
Explicit Methods
Sparse matrix
Spectral Analysis
Positive definite
Numerical Experiment
Robustness
Unknown
Coefficient
Graph in graph theory

Keywords

  • Krylov subspace method
  • domain decomposition
  • general sparse linear system
  • low-rank approximation
  • parallel preconditioner
  • the Lanczos algorithm

Cite this

Schur complement-based domain decomposition preconditioners with low-rank corrections. / Li, Ruipeng; XI, Yuanzhe; Saad, Yousef.

In: Numerical Linear Algebra with Applications, Vol. 23, No. 4, 01.08.2016, p. 706-729.

Research output: Contribution to journalArticle

@article{43f398145ab54f61a6552afef057ee36,
title = "Schur complement-based domain decomposition preconditioners with low-rank corrections",
abstract = "This paper introduces a robust preconditioner for general sparse matrices based on low-rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low-rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach.",
keywords = "Krylov subspace method, domain decomposition, general sparse linear system, low-rank approximation, parallel preconditioner, the Lanczos algorithm",
author = "Ruipeng Li and Yuanzhe XI and Yousef Saad",
year = "2016",
month = "8",
day = "1",
doi = "10.1002/nla.2051",
language = "English (US)",
volume = "23",
pages = "706--729",
journal = "Numerical Linear Algebra with Applications",
issn = "1070-5325",
publisher = "John Wiley and Sons Ltd",
number = "4",

}

TY - JOUR

T1 - Schur complement-based domain decomposition preconditioners with low-rank corrections

AU - Li, Ruipeng

AU - XI, Yuanzhe

AU - Saad, Yousef

PY - 2016/8/1

Y1 - 2016/8/1

N2 - This paper introduces a robust preconditioner for general sparse matrices based on low-rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low-rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach.

AB - This paper introduces a robust preconditioner for general sparse matrices based on low-rank approximations of the Schur complement in a Domain Decomposition framework. In this ‘Schur Low Rank’ preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low-rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach.

KW - Krylov subspace method

KW - domain decomposition

KW - general sparse linear system

KW - low-rank approximation

KW - parallel preconditioner

KW - the Lanczos algorithm

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

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

U2 - 10.1002/nla.2051

DO - 10.1002/nla.2051

M3 - Article

VL - 23

SP - 706

EP - 729

JO - Numerical Linear Algebra with Applications

JF - Numerical Linear Algebra with Applications

SN - 1070-5325

IS - 4

ER -