Domain Decomposition Methods for Partial Differential Equations

Domain decomposition, a form of divide-and-conquer for mathematical problems posed over a physical domain is the most common paradigm for large-scale simulation on massively parallel, distributed, hierarchical memory computers. In domain decomposition, a large problem is reduced to a collection of smaller problems, each of which is easier to solve computationally than the undecomposed problem, and most or all of which can be solved independently and concurrently. Domain decomposition has proved to be an ideal paradigm not only for execution on advanced architecture computers, but also for the development of reusable, portable software. The most complex operation in a typical domain decomposition method -- the application of the preconditioner -- carries out in each subdomain steps nearly identical to those required to apply a conventional preconditioner to the undecomposed domain. Hence software developed for the global problem can readily be harvested for the local problems of a parallel implementation.
Finally, it should be noted that domain decomposition is often a natural paradigm for the modeling community. Physical systems are often decomposed into two or more contiguous subdomains based on phenomenological considerations, such as the importance or negligibility of viscosity or reactivity, or any other feature, and the subdomains are discretized accordingly, as independent tasks. This physically-based domain decomposition may be mirrored in the software engineering of the corresponding code, and leads to threads of execution that operate on contiguous subdomain blocks. This tutorial provides an overview of domain decomposition and focuses on the mathematical development of its two main paradigms: Schwarz (projection) and Schur (block elimination) preconditioning and their hybrids and nonlinear generalizations.