Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods

J. M. Tang, R. Nabben, C. Vuik, Y. A. Erlangga

Research output: Contribution to journalArticle

53 Citations (Scopus)

Abstract

For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.

Original languageEnglish
Pages (from-to)340-370
Number of pages31
JournalJournal of Scientific Computing
Volume39
Issue number3
DOIs
Publication statusPublished - Jun 2009
Externally publishedYes

Fingerprint

Deflation
Multigrid Method
Domain Decomposition Method
Preconditioner
Decomposition
Two-level Method
Linear systems
Sparse Linear Systems
Smallest Eigenvalue
Rounding error
Largest Eigenvalue
Coefficient
Domain Decomposition
Spectral Properties
Positive definite
Termination
Convergence Properties
Equivalence
Projection
Robustness

Keywords

  • Conjugate gradients
  • Deflation
  • Domain decomposition
  • Multigrid
  • SPD matrices
  • Two-grid schemes
  • Two-level PCG methods
  • Two-level preconditioning

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Theoretical Computer Science
  • Engineering(all)

Cite this

Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods. / Tang, J. M.; Nabben, R.; Vuik, C.; Erlangga, Y. A.

In: Journal of Scientific Computing, Vol. 39, No. 3, 06.2009, p. 340-370.

Research output: Contribution to journalArticle

Tang, J. M. ; Nabben, R. ; Vuik, C. ; Erlangga, Y. A. / Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods. In: Journal of Scientific Computing. 2009 ; Vol. 39, No. 3. pp. 340-370.
@article{584a48990f0d40e7937a8d63ae5d116f,
title = "Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods",
abstract = "For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.",
keywords = "Conjugate gradients, Deflation, Domain decomposition, Multigrid, SPD matrices, Two-grid schemes, Two-level PCG methods, Two-level preconditioning",
author = "Tang, {J. M.} and R. Nabben and C. Vuik and Erlangga, {Y. A.}",
year = "2009",
month = "6",
doi = "10.1007/s10915-009-9272-6",
language = "English",
volume = "39",
pages = "340--370",
journal = "Journal of Scientific Computing",
issn = "0885-7474",
publisher = "Springer New York",
number = "3",

}

TY - JOUR

T1 - Comparison of two-level preconditioners derived from deflation, domain decomposition and multigrid methods

AU - Tang, J. M.

AU - Nabben, R.

AU - Vuik, C.

AU - Erlangga, Y. A.

PY - 2009/6

Y1 - 2009/6

N2 - For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.

AB - For various applications, it is well-known that a multi-level, in particular two-level, preconditioned CG (PCG) method is an efficient method for solving large and sparse linear systems with a coefficient matrix that is symmetric positive definite. The corresponding two-level preconditioner combines traditional and projection-type preconditioners to get rid of the effect of both small and large eigenvalues of the coefficient matrix. In the literature, various two-level PCG methods are known, coming from the fields of deflation, domain decomposition and multigrid. Even though these two-level methods differ a lot in their specific components, it can be shown that from an abstract point of view they are closely related to each other. We investigate their equivalences, robustness, spectral and convergence properties, by accounting for their implementation, the effect of roundoff errors and their sensitivity to inexact coarse solves, severe termination criteria and perturbed starting vectors.

KW - Conjugate gradients

KW - Deflation

KW - Domain decomposition

KW - Multigrid

KW - SPD matrices

KW - Two-grid schemes

KW - Two-level PCG methods

KW - Two-level preconditioning

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

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

U2 - 10.1007/s10915-009-9272-6

DO - 10.1007/s10915-009-9272-6

M3 - Article

VL - 39

SP - 340

EP - 370

JO - Journal of Scientific Computing

JF - Journal of Scientific Computing

SN - 0885-7474

IS - 3

ER -