# Domain Decomposition

## Parallel Multilevel Methods for Elliptic Partial Differential Equations

The emergence of parallel computers and their potential for the numerical solution of Grand Challenge problems has led to a large amount of research in domain decomposition methods. This book presents an easy-to-read discussion of domain decomposition algorithms, their implementation and analysis. This book is ideal for graduate students about to embark on a career in computational science. It will also be a valuable resource for all those interested in parallel computing and numerical computational methods.

Cambridge University Press: Europe- North America

ISBN 0-521-49589-X

## Features

• Complete descriptions of most standard domain decomposition, multilevel, and multigrid algorithms.
• All algorithms carefully presented using easy-to-understand matrix notation.
• Numerical results indicating the fundamental behavior of the algorithms.
• Careful development of the convergence theory for these methods written for a wide audience.
• Discussion of parallel implementations of these methods.

• Chapter 1: One Level Algorithms
• 1.1 Classical Alternating Schwarz Method
• 1.2 Approximate Solvers
• 1.3 Many Subdomains
• 1.4 Convergence Behavior
• 1.5 Implementation Issues
• 1.6 Variational Formulation
• Chapter 2: Two Level Algorithms
• 2.1 Subdomain Solves Are Not Sufficient
• 2.2 A Simple Two Level Method
• 2.3 General Two Level Methods
• 2.4 Coarse Grid Corrections
• 2.5 Convergence Behavior
• 2.6 Implementation Issues
• 2.7 Fourier Analysis of Two Level Methods
• 2.8 Variational Formulation
• Chapter 3: Multilevel Algorithms
• 3.1 Additive Multilevel Schwarz Methods
• 3.2 Multiplicative Multilevel Schwarz Methods
• 3.3 Full Multigrid
• 3.4 Practical Multilevel Methods
• 3.5 Multilevel Methods as Classical Jacobi and Gauss-Seidel
• 3.6 Complexity Issues
• 3.7 Implementation Issues
• 3.8 Variational Formulation
• Chapter 4: Substructuring Methods
• 4.1 Direct Substructuring Methods
• 4.2 The Two Subdomain Case
• 4.3 Many Subdomains
• 4.4 Inexact Subdomain Solves
• 4.5 Implementation Issues
• 4.6 Variational Formulation
• Chapter 5: A Convergence Theory
• 5.1 Abstract Convergence Analysis
• 5.2 Analysis of Standard Methods
• 5.3 Indefinite and Nonsymmetric Problems
• Appendix 1: Preconditioners and Accelerators
• Appendix 2: Software for Numerical Parallel Computing
• ## Errata

• Page 15, Computational results 1.1.2 In these comparisons alternating Schwarz refers to alternating Schwarz without a Krylov accelerator while multiplicative Schwarz is (because the grids match) alternating Schwarz with GMRES acceleration.
• Page 34, line 13. "partioning" should be "partitioning".
• Page 36, line 4. "Find v_1 \element V_1" should be "Find e_1 \element V_1".
• Page 57, line 24, "A_{h} u = 1/h^{2} (...) u = f" should be "A_{h} u = 1/h (...) u = h f".
• Page 58, line 21, "A_{H} = 1/H^{2}(....)" should be A_{H} = 1/H(....)".
• Page 85, the boxed algorithm at the top of the page should be labeled Algorithm 3.3.1
• Page 99, line 16. "that it helpful" should be "that it is helpful".
• Page 103, line 15,"(5 and 20 ..." should be "(5 or 6 and 20 ..."
• Page 103, line 19,remove ",but this time"
• Page 106, line 15, The sentence beginning "Using this, we see ... u^{(i)}_{B}." should be removed.
• Page 106, Equation (4.1) should NOT have the \tilde{R}_{i} next to the f_{I}^{(i)}
• Page 107, line 22. "competely" should be "completely".
• Page 113, equation above (4.5) should have a "g" on the right hand side rather than "f_B"
• Page 137, the expression z^{(i)}z^{(i)T}/z^{(i)T}z^{(i)} should be z^{(i)}z^{(i)T}\hat{S}^{(i)}/z^{(i)T}\hat{S}^{(i)}z^{(i)} because the projection is in the inner product induced by \hat{S}^{(i)}.
• Page 153, the symmetric forms of the algorithms only make sense when the operator A and the preconditioners B_i are all symmetric
• Page 172, line 16. "Cr^{-2} \sum ..." should be "C \sum r^{-2} ..." since "r" is a function of the elements being summed over.
• Page 220, line 16. "Lois Curfman McInncs" should be "Lois Curfman McInnes".
• Page 224. "Mathew, J. P." should be "Mathew, T. P."
• Page 224. "Wheeler, N. F." should be "Wheeler, M. F."
• ## Related Materials

• PETSc: Parallel numerical software for PDES.
• MG-NET: Multigrid/Domain Decomposition database.