NYCCS/Computer Science Seminar
David Keyes, Monday August 4, 2008
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 adapted to the local problem, instantly
presenting lots of legacy scientific code for to be harvested for parallel
implementations. 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 and Schur preconditioning and their hybrids, and their
implementation in software available from TOPS and contributors.