Mathematical analysis of robustness of two-level domain decomposition methods with respect to inexact coarse solves

Abstract

Convergence of domain decomposition methods rely heavily on the efficiency of the coarse space used in the second level. The GenEO coarse space has been shown to lead to a robust two-level Schwarz preconditioner which scales well over multiple cores (Spillane et al. in Numer Math 126(4):741–770, 2014. https://doi.org/10.1007/s00211-013-0576-y; Dolean et al. in An introduction to domain decomposition methods: algorithms, theory and parallel implementation, SIAM, Philadelphia, 2015). The robustness is due to its good approximation properties for problems with highly heterogeneous material parameters. It is available in the finite element packages FreeFem++ (Hecht in J Numer Math 20(3–4):251–265, 2012), Feel++ (Prud’homme in Sci Program 14(2):81–110, 2006), Dune (Blatt et al. in Arch Numer Softw 4(100):13–29, 2016) and is implemented as a standalone library in HPDDM (Jolivet and Nataf in HPDDM: high-Performance Unified framework for Domain Decomposition methods, MPI-C++ library, 2014. https://github.com/hpddm/hpddm) and as such is available as well as a PETSc (Balay et al. in: Arge, Bruaset, Langtangen, (eds) Modern software tools in scientific computing, Birkhäuser Press, Basel, 1997) preconditioner. But the coarse component of the preconditioner can ultimately become a bottleneck if the number of subdomains is very large and exact solves are used. It is therefore interesting to consider the effect of inexact coarse solves. In this paper, robustness of GenEO methods is analyzed with respect to inexact coarse solves. Interestingly, the GenEO-2 method introduced in Haferssas et al. (SIAM J Sci Comput 39(4):A1345–A1365, 2017. https://doi.org/10.1137/16M1060066) has to be modified in order to be able to prove its robustness in this context.

Annex

We explain here how to adapt the GenEO coarse space as defined in [3] so that it will behave as the one defined in [20]. In one sentence, it consists simply in computing the local components of the coarse space on the subdomain extended by one layer (or more).

More precisely, we start from a domain decomposition $(\Omega _i)_{1\le i \le N}$ and inherited indices decomposition $({\mathcal N}_i)_{1\le i \le N}$ as defined in the present article. Let us denote with a tilde $\tilde{}$ all the quantities related to the subdomains $\Omega _{\tilde{i}}$ obtained by extending by one (or more) layers of cells subdomains $\Omega _i$, see Fig. 1. Similarly to [3], we define

$$\begin{aligned} {\mathcal N}_{\tilde{i}} := \{ k \in {\mathcal N}\ | \ meas(Supp(\phi _k)\cap \Omega _{\tilde{i}})>0\}. \end{aligned}$$

Fig. 1

A subdomain and its extension by one layer

Since $\Omega _i \subset \Omega _{\tilde{i}}$ , we have

$$\begin{aligned} {\mathcal N}_i \subset {\mathcal N}_{\tilde{i}} . \end{aligned}$$

Also from the partition of unity on the original decomposition, we can define a partition of unity on $({\mathcal N}_{\tilde{i}})_{1\le i\le N}$ inherited from the one on $({\mathcal N}_i)_{1\le i\le N}$ by defining diagonal matrices $(D_{\tilde{i}})_{1\le i \le N}$ in the following manner:

$$\begin{aligned} (D_{\tilde{i}})_{kk} := \left\{ \begin{array}{lcl} (D_i)_{kk} &{}\text { if }&{} k\in {\mathcal N}_i \\ 0 &{}\text { if }&{} k\in {\mathcal N}_{\tilde{i}} \backslash {\mathcal N}_i \end{array} \right. . \end{aligned}$$

We have clearly a partition of unity:

$$\begin{aligned} {I}_{} = \sum _{i=1}^N R_{\tilde{i}}^T D_{\tilde{i}} R_{\tilde{i}}. \end{aligned}$$

Also since for all subdomains $1\le i\le N$, the entries of $D_{\tilde{i}}$ are zero on the added layers, we have the following equality:

$$\begin{aligned} D_i R_i = R_i R_{\tilde{i}}^T D_{\tilde{i}} R_{\tilde{i}}. \end{aligned}$$

The coarse space is built by first introducing the Neumann matrices $A_{\tilde{i}}^{Neu}$ on subdomains $\Omega _{\tilde{i}}$ for $1\le i \le N$, as in [20], so that we have:

$$\begin{aligned} \sum _{i=1}^N (A_{\tilde{i}}^{Neu} R_{\tilde{i}}{\mathbf {U}},\,R_{\tilde{i}}{\mathbf {U}}) \le {\widetilde{k_1}} (A {\mathbf {U}},\,{\mathbf {U}}), \end{aligned}$$

where ${\widetilde{k_1}}$ is the maximum multiplicity of the intersections of subdomains $\Omega _{\tilde{i}}$. Let $V_{\tilde{i}k}$ be the eigenvectors of the following generalized eigenvalue problem:

$$\begin{aligned} D_{\tilde{i}}\, R_{\tilde{i}}\,A\,R_{\tilde{i}}^T\,D_{\tilde{i}}\, V_{\tilde{i}k} = \lambda _{ik} A_{\tilde{i}}^{Neu}\, V_{\tilde{i}k}. \end{aligned}$$

Note that for $\lambda _{\tilde{i}k}$ not equal to 1, the eigenvectors are harmonic for the interior degrees of freedom since for these points the left and right matrices have identical entries for the corresponding lines. Thus, for $\lambda _{\tilde{i}k} \ne 1$, we might as well zero the lines corresponding the interior degrees of freedom and keep only the entries of the degrees of freedom in the overlap. This GEVP is thus also of the type GenEO.

For a user-defined parameter $\tau$, let us define the coarse space as follows:

$$\begin{aligned} V_0 := Span\{ R_{\tilde{i}}^T\,D_{\tilde{i}}\, V_{\tilde{i}k}\ |\ 1 \le i \le N,\ \lambda _{ik} > \tau \}, \end{aligned}$$

and a rectangular matrix $Z\in \mathbb {R}^{\#{\mathcal N}\times \#{\mathcal N}_0}$ whose columns are a basis of $V_0$ where ${\mathcal N}_0$ is a set of indices whose cardinal is the dimension of the vector space $V_0$. We also define local projections $(\pi _{\tilde{i}})_{1\le i \le N}$ on $Span\{ V_{\tilde{i}k}\ |\,\ \lambda _{ik} > \tau \}$ parallel to $Span\{ V_{\tilde{i}k}\ |\,\ \lambda _{ik} \le \tau \}$.

We have then a stable decomposition. Indeed, let ${\mathbf {U}}\in \mathbb {R}^{\#{\mathcal N}}$,

$$\begin{aligned} {\mathbf {U}} = \sum _{i=1}^N R_i^T D_i R_i {\mathbf {U}} = \sum _{i=1}^N R_i^T R_i R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}) + \sum _{i=1}^N R_i^T R_i R_{\tilde{i}}^T D_{\tilde{i}} \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}. \end{aligned}$$

The last term is clearly in $V_0$ so that there exists ${\mathbf {U}}_0\in \mathbb {R}^{{\mathcal N}_0}$ such that

$$\begin{aligned} Z {\mathbf {U}}_0 = \sum _{i=1}^N R_i^T R_i R_{\tilde{i}}^T D_{\tilde{i}} \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}} = \sum _{i=1}^N R_{\tilde{i}}^T D_{\tilde{i}} \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}} \in V_0. \end{aligned}$$

Let us define

$$\begin{aligned} {\mathbf {U}}_i := R_i R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}). \end{aligned}$$

This decomposition is stable since

$$\begin{aligned}&\sum _{i=1}^N (A R_i^T {\mathbf {U}}_i ,\,R_i^T{\mathbf {U}}_i )\\&\quad = \sum _{i=1}^N (A R_i^T R_i R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}) ,\, R_i^T R_i R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}) ) \\&\quad = \sum _{i=1}^N (A R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}) ,\, R_{\tilde{i}}^T D_{\tilde{i}} ( R_{\tilde{i}} {\mathbf {U}} - \pi _{\tilde{i}} R_{\tilde{i}} {\mathbf {U}}) ) \\&\quad \le \tau \sum _{i=1}^N (A_{\tilde{i}}^{Neu} R_{\tilde{i}} {\mathbf {U}} ,\, R_{\tilde{i}} {\mathbf {U}} ) \le \tau \widetilde{k_1}\, (A{\mathbf {U}} ,\, {\mathbf {U}} ). \end{aligned}$$

Note also that Assumption 2.1 of [20] is automatically satisfied in the finite element framework chosen here whereas Assumptions 3.12 and 3.13 of [20] are not needed here since our construction is simpler.