Domain Decomposition

Parallel Multilevel Methods for Elliptic Partial Differential Equations

Barry Smith, Petter Bjorstad, and William Gropp

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.

    • Table of Contents

  • 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 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."