Multilevel Extension Techniques in Domain Decomposition Preconditioners

Gundolf Haase
Johannes Kepler University
Institut für Mathematik
A-4040 Linz, Altenbergerstrasse 69, Austria


One component in Additive Schwarz Method (ASM) Domain Decomposition (DD) preconditioners [BPS89, SBG96] using inexact subdomain solvers [Boe89, HLM91] consists in an operator extending the boundary data into the interior of each subdomain, i.e., a homogeneous extension with respect to the differential operator given in that subdomain. This paper is concerned with the construction of cheap extension operators using multilevel nodal bases [Yse86, Xu89, BPX90, Osw94] from an implementation viewpoint. Additional smoothing sweeps in the extension operators further improve the condition number of the preconditioned system. The paper summarizes and improves results given in [HLMN94, Nep95, Haa97].

References in Abstract

[Boe89] Boergers M. (1989) The Neumann-Dirichlet domain decomposition method with inexact solvers on the subdomains. Numerische Mathematik 55(2):123-136.

[BPS89] Bramble J., Pasciak J., and Schatz A. (1986, 1987, 1988, 1989) The construction of preconditioners for elliptic problems by substructuring I-IV. Mathematics of Computation 47:103-134, 49:1-16, 51:415-430, 53:1-24.

[BPX90] Bramble J., Pasciak J., and Xu J. (1990) Parallel multilevel preconditioners. Mathematics of Computation 55(191):1-22.

[Haa97] Haase G. (May 1997) Hierarchical extension operators plus smoothing in domain decomposition preconditioners. Applied Numerical Mathematics 23(3).

[HLM91] Haase G., Langer U., and Meyer A. (1991) The approximate Dirichlet domain decompositionmethod. Part I: An algebraic approach. Part II: Applications to 2nd-order elliptic boundary value problems. Computing 47:137-151 (Part I), 47:153-167 (Part II).

[HLMN94] Haase G., Langer U., Meyer A., and Nepomnyaschikh S.(1994) Hierarchical extension operators and local multigrid methods in domain decomposition preconditioners. East-West Journal of Numerical Mathematics 2:173-193.

[Nep95] Nepomnyaschikh S. (1995) Optimal multilevel extension operators. Report 95-3, TU Chemnitz.

[Osw94] Oswald P. (1994) Multilevel Finite Element Approximation. Teubner.

[SBG96] Smith B., Bjorstad P., and Gropp W. (1996) Domain Decomposition: parallel methods for elliptic partial differential equations. Cambridge University Press.

[Xu89] Xu J. (1989) Theory of multilevel methods. Technical Report AM48, Department of Mathematics, Penn State University.

[Yse86] Yserentant H. (1986) On the multi-level splitting of finite element spaces. Numer. Math. 49(4):379-412.

Contributed November 27, 1997.