Domain decomposition: A bridge between nature and parallel computers

Domain decomposition is an intuitive organizing principle for a PDE computation, both physically and architecturally. However, its significance extends beyond the readily apparent issues of geometry and discretization, on one hand, and of modular software and distributed hardware, on the other. Engineering and computer science aspects are bridged by an old but recently enriched mathematical theory that offers the subject not only unity, but also tools for analysis and generalization. Domain decomposition induces function-space and operator decompositions with valuable properties. Function-space bases and operator splittings that are not derived from domain decompositions generally lack one or more of these properties. The evolution of domain decomposition methods for elliptically dominated problems has linked two major algorithmic developments of the last 15 years: multilevel and Krylov methods. Domain decomposition methods may be considered descendants of both classes with an inheritance from each: they are nearly optimal and at the same time efficiently parallelizable. Many computationally driven application areas are ripe for these developments. This paper progresses from a mathematically informal motivation for domain decomposition methods to a specific focus on fluid dynamics applications. Introductory rather than comprehensive, it employs simple examples, and leaves convergence proofs and algorithmic details to the original references; however, an attempt is made to convey their most salient features, especially where this leads to algorithmic insight.