Robust domain decomposition algorithms for multiscale PDEs

In this article, we describe a new class of domain decomposition preconditioners suitable for solving elliptic PDEs in highly fractured or heterogeneous media, such as arise in groundwater flow or oil recovery applications. Our methods employ novel coarsening operators, which are adapted to the heterogeneity of the media. In contrast to standard methods (based on piecewise polynomial coarsening), the new methods can achieve robustness with respect to coefficient discontinuities even when these are not resolved by a coarse mesh. This Situation arises often in practical flow computation, in both the deterministic and (Monte-Carlo simulated) stochastic cases. An example of a suitable coarsener is provided by multiscale finite elements. In this article, we explore the linear algebraic aspects of the multiscale algorithm, showing that it involves a blend of both classical overlapping Schwarz methods and nonoverlapping Schur methods. We also extend the algorithm and the theory from its additive variant to obtain new hybrid and deflation variants. Finally, we give extensive numerical experiments on a range of heterogeneous media problems illustrating the properties of the methods. (c) 2007 Wiley Periodicals, Inc.