Domain Decomposition

Parallel Multilevel Methods for Elliptic Partial Differential Equations

Barry Smith, Petter Bjorstad, and William Gropp

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

Domain Decomposition will be available at your favorite bookstore or order directly from Cambridge.

Ordering Information

  • North America: Price $39.95. Telephone orders 1-800-872-7423. Electronic orders.
  • Australia: Cambridge University Press, Australian Branch, 10 Stamford Rd (or P.O. Box 85), Oakleigh, Victoria. 3166. Phone: 03 568 0322. Fax: 03 568 1517.
  • Europe and elsewhere: Customer Services Dept, Cambridge University Press, The Edinburgh Building, Cambridge CB2 2RU, UK. Phone: +44 (1223) 325970. Fax: +44 (1223) 325959. Email: Trade@cup.cam.ac.uk.

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

    • Related Materials

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