Scaling up through domain decomposition

Abstract

In this article, we discuss domain decomposition parallel iterative solvers for highly heterogeneous problems of flow and transport in porous media. We are particularly interested in highly unstructured coefficient variation where standard periodic or stochastic homogenization theory is not applicable. When the smallest scale at which the coefficient varies is very small, it is often necessary to scale up the equation to a coarser grid to make the problem computationally feasible. Standard upscaling or multiscale techniques require the solution of local problems in each coarse element, leading to a computational complexity that is at least linear in the global number N of unknowns on the subgrid. Moreover, except for the periodic and the isotropic random case, a theoretical analysis of the accuracy of the upscaled solution is not yet available. Multilevel iterative methods for the original problem on the subgrid, such as multigrid or domain decomposition, lead to similar computational complexity (i.e. 𝒪(N)) and are therefore a viable alternative. However, previously no theory was available guaranteeing the robustness of these methods to large coefficient variation. We review a sequence of recent papers where simple variants of domain decomposition methods, such as overlapping Schwarz and one-level FETI, are proposed that are robust to strong coefficient variation. Moreover, we also extend the theoretical results, for the first time, to the dual-primal variant of FETI.

Keywords:

• multiscale PDEs
• numerical homogenization
• parallel iterative solvers
• additive Schwarz
• FETI
• conditioning analysis

AMS Subject Classifications::

• 65N55
• 65F10
• 35B27
• 74Q15
• 76S05

Acknowledgement

C. Pechstein was supported by the Austrian Science Fund (FWF) under grant P19255.

Notes

Notes

1. In this article, we use the term ‘scaling up’ in the sense of solving larger and larger physical problems, which is equivalent to letting ϵ → 0 on a fixed size domain.

2. AMG and the related BoxMG 23 have also recently been used in the context of numerical homogenization in 24–26, but this is not the topic of this article.