Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs

J Van Lent, R Scheichl, I G Graham

Research output: Contribution to journalArticle

26 Citations (Scopus)

Abstract

Two-level overlapping Schwarz methods for elliptic partial differential equations combine local solves on overlapping domains with a global solve of a coarse approximation of the original problem. To obtain robust methods for equations with highly varying coefficients, it is important to carefully choose the coarse approximation. Recent theoretical results by the authors have shown that bases for such robust coarse spaces should be constructed such that the energy of the basis functions is minimized. We give a simple derivation of a method that finds such a minimum energy basis using one local solve per coarse space basis function and one global solve to enforce a partition of unity constraint. Although this global solve may seem prohibitively expensive, we demonstrate that a one-level overlapping Schwarz method is an effective and scalable preconditioner and we show that such a preconditioner can be implemented efficiently using the Sherman-Morrison-Woodbury formula. The result is an elegant, scalable, algebraic method for constructing a robust coarse space given only the supports of the coarse space basis functions. Numerical experiments on a simple two-dimensional model problem with a variety of binary and multiscale coefficients confirm this. Numerical experiments also show that, when used in a two-level preconditioner, the energy-minimizing coarse space gives better results than other coarse space constructions, such as the multiscale finite element approach. Copyright (C) 2009 John Wiley & Sons, Ltd.
Original languageEnglish
Pages (from-to)775-799
Number of pages25
JournalNumerical Linear Algebra with Applications
Volume16
Issue number10
DOIs
Publication statusPublished - Oct 2009

Fingerprint

Two-level Method
Schwarz Methods
Energy
Preconditioner
Overlapping
Basis Functions
Partial differential equations
Experiments
Sherman-Morrison Formula
Numerical Experiment
Partition of Unity
Varying Coefficients
Algebraic Methods
Elliptic Partial Differential Equations
Robust Methods
Approximation
Choose
Binary
Finite Element
Coefficient

Cite this

Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs. / Van Lent, J; Scheichl, R; Graham, I G.

In: Numerical Linear Algebra with Applications, Vol. 16, No. 10, 10.2009, p. 775-799.

Research output: Contribution to journalArticle

@article{e1da45e13c944d1691c1d47d6e016c94,
title = "Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs",
abstract = "Two-level overlapping Schwarz methods for elliptic partial differential equations combine local solves on overlapping domains with a global solve of a coarse approximation of the original problem. To obtain robust methods for equations with highly varying coefficients, it is important to carefully choose the coarse approximation. Recent theoretical results by the authors have shown that bases for such robust coarse spaces should be constructed such that the energy of the basis functions is minimized. We give a simple derivation of a method that finds such a minimum energy basis using one local solve per coarse space basis function and one global solve to enforce a partition of unity constraint. Although this global solve may seem prohibitively expensive, we demonstrate that a one-level overlapping Schwarz method is an effective and scalable preconditioner and we show that such a preconditioner can be implemented efficiently using the Sherman-Morrison-Woodbury formula. The result is an elegant, scalable, algebraic method for constructing a robust coarse space given only the supports of the coarse space basis functions. Numerical experiments on a simple two-dimensional model problem with a variety of binary and multiscale coefficients confirm this. Numerical experiments also show that, when used in a two-level preconditioner, the energy-minimizing coarse space gives better results than other coarse space constructions, such as the multiscale finite element approach. Copyright (C) 2009 John Wiley & Sons, Ltd.",
author = "{Van Lent}, J and R Scheichl and Graham, {I G}",
year = "2009",
month = "10",
doi = "10.1002/nla.641",
language = "English",
volume = "16",
pages = "775--799",
journal = "Numerical Linear Algebra with Applications",
issn = "1070-5325",
publisher = "John Wiley and Sons Inc.",
number = "10",

}

TY - JOUR

T1 - Energy-minimizing coarse spaces for two-level Schwarz methods for multiscale PDEs

AU - Van Lent, J

AU - Scheichl, R

AU - Graham, I G

PY - 2009/10

Y1 - 2009/10

N2 - Two-level overlapping Schwarz methods for elliptic partial differential equations combine local solves on overlapping domains with a global solve of a coarse approximation of the original problem. To obtain robust methods for equations with highly varying coefficients, it is important to carefully choose the coarse approximation. Recent theoretical results by the authors have shown that bases for such robust coarse spaces should be constructed such that the energy of the basis functions is minimized. We give a simple derivation of a method that finds such a minimum energy basis using one local solve per coarse space basis function and one global solve to enforce a partition of unity constraint. Although this global solve may seem prohibitively expensive, we demonstrate that a one-level overlapping Schwarz method is an effective and scalable preconditioner and we show that such a preconditioner can be implemented efficiently using the Sherman-Morrison-Woodbury formula. The result is an elegant, scalable, algebraic method for constructing a robust coarse space given only the supports of the coarse space basis functions. Numerical experiments on a simple two-dimensional model problem with a variety of binary and multiscale coefficients confirm this. Numerical experiments also show that, when used in a two-level preconditioner, the energy-minimizing coarse space gives better results than other coarse space constructions, such as the multiscale finite element approach. Copyright (C) 2009 John Wiley & Sons, Ltd.

AB - Two-level overlapping Schwarz methods for elliptic partial differential equations combine local solves on overlapping domains with a global solve of a coarse approximation of the original problem. To obtain robust methods for equations with highly varying coefficients, it is important to carefully choose the coarse approximation. Recent theoretical results by the authors have shown that bases for such robust coarse spaces should be constructed such that the energy of the basis functions is minimized. We give a simple derivation of a method that finds such a minimum energy basis using one local solve per coarse space basis function and one global solve to enforce a partition of unity constraint. Although this global solve may seem prohibitively expensive, we demonstrate that a one-level overlapping Schwarz method is an effective and scalable preconditioner and we show that such a preconditioner can be implemented efficiently using the Sherman-Morrison-Woodbury formula. The result is an elegant, scalable, algebraic method for constructing a robust coarse space given only the supports of the coarse space basis functions. Numerical experiments on a simple two-dimensional model problem with a variety of binary and multiscale coefficients confirm this. Numerical experiments also show that, when used in a two-level preconditioner, the energy-minimizing coarse space gives better results than other coarse space constructions, such as the multiscale finite element approach. Copyright (C) 2009 John Wiley & Sons, Ltd.

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

UR - http://dx.doi.org/10.1002/nla.641

U2 - 10.1002/nla.641

DO - 10.1002/nla.641

M3 - Article

VL - 16

SP - 775

EP - 799

JO - Numerical Linear Algebra with Applications

JF - Numerical Linear Algebra with Applications

SN - 1070-5325

IS - 10

ER -