An Adaptive GDSW Coarse Space for Two-Level Overlapping Schwarz Methods in Two Dimensions

Abstract

We propose robust coarse spaces for two-level overlapping Schwarz preconditioners, which are extensions of the energy minimizing coarse space known as GDSW (Generalized Dryja, Smith, Widlund). The resulting two-level methods with adaptive coarse spaces are robust for second order elliptic problems in two dimensions, even in presence of a highly heterogeneous coefficient function, and reduce to the standard GDSW algorithm if no additional coarse basis functions are used.

1 Introduction

We consider the second order elliptic problem in two dimensions

$$\displaystyle \begin{aligned} \begin{aligned} - \nabla \cdot \left( A(x) \nabla u(x) \right) & = f(x) & & \mbox{in} \ \varOmega \subset \mathbb{R}^2, \\ u & = 0 & & \mbox{on} \ \partial\varOmega, \end{aligned} \end{aligned} $$

(1)

where the scalar coefficient function A(x) > 0 is highly heterogeneous, possibly with high jumps. We propose a coarse space for two-level overlapping Schwarz methods with a condition number bound independent of the coefficient. Our approach extends the GDSW (Generalized Dryja, Smith, Widlund) method [7, 8] since it always contains the classic GDSW coarse space. Originally, the method was inspired by the ACMS (Approximate Component Mode Synthesis) special finite element method [14, 17], which uses enrichment by local eigenfunctions. The ACMS space was first considered as a coarse space for domain decomposition (DD) in [15].

In two dimensions, our new coarse space consists of simple nodal finite element functions and of energy minimizing extensions of solutions of generalized eigenvalue problems on the edges. See [16] for the description of the three-dimensional case and the proof of the condition number bound. A related method is the SHEM (Spectral Harmonically Enriched Multiscale) coarse space, introduced in [12], however, our eigenvalue problems do not use mass matrices; see (5). In our new coarse space and in the one based on the ACMS discretization method, the construction of the generalized eigenvalue problems is computationally slightly more expensive than in the SHEM coarse space [12]. However, the dimension of the coarse space can be reduced significantly in certain cases. Earlier coarse spaces for overlapping Schwarz methods, which also use mass matrices, are, e.g., [9,10,11]. These eigenvalue problems are used to replace local Poincaré inequalities.

To the best of our knowledge the use of local eigenvalue problems has been introduced to DD in [2, 3]. Successful adaptive FETI-DP and BDDC methods were given in [18] followed, e.g., by [19]. Local eigenvalue problems have also been used in the algebraic multigrid (AMG) community [4, 6]. The ACMS discretization method is related to other multiscale discretization methods. Notable contributions in DD for multiscale problems are [1, 5, 13].

The variational problem corresponding to (1) reads: find $u \in {{H_0^1(\varOmega )}}$, such that

$$\displaystyle \begin{aligned} {a_{\varOmega} \left( {u} , {v} \right) } = L(v) \qquad \forall v \in {{H_0^1(\varOmega)}} \end{aligned} $$

(2)

and ${a_{\varOmega } \left ( {u} , {v} \right ) } := \int _\varOmega (\nabla u(x))^T A(x) \nabla v(x)\,dx \,,$ $L\left ( {v} \right ) := \int _\varOmega f(x) v(x)\,dx,$ where f ∈ L ²(Ω). We define the semi-norm corresponding to the bilinear form ${a_{\varOmega } \left ( {\cdot } , {\cdot } \right ) }$ as ${\left | {u} \right |{ }_{a,\varOmega }}^2 := {a_{\varOmega } \left ( {u} , {u} \right ) }$. Let Ku = f be the discretization of problem (2) by piecewise linear or bilinear finite elements on a family of triangulations $\left (\tau _h\right )_h$.

1.1 The Standard GDSW Preconditioner

The GDSW preconditioner [7, 8] is a two-level additive overlapping Schwarz preconditioner with exact solvers; cf. [20]. It can therefore be written in the form

$$\displaystyle \begin{aligned} M_{\mathrm GDSW}^{-1} = \varPhi K_0^{-1} \varPhi^T + \sum_{i=1}^{N} R_i^T {\tilde K_i}^{-1} R_i, \end{aligned} $$

(3)

where K ₀ = Φ ^TKΦ and ${\tilde K_i} = R_i^T K R_i$. The matrices R _i are the restriction operators to the overlapping subdomains $\tilde \varOmega _i$, i = 1, …, N. The columns of Φ are the coarse basis functions. These use discrete harmonic extensions of interface functions into the interior of the nonoverlapping subdomains. On the interface, the values are defined as the restrictions of the nullspace of the operator to the edges and vertices of the nonoverlapping domain decomposition. The condition number estimate for the GDSW Schwarz operator, in case of a constant coefficient function A, is

$$\displaystyle \begin{aligned} \kappa \left( M_{\mathrm GDSW}^{-1} K \right) \leq C \left(1+{H}/{\delta}\right)\left( 1 + \log\left({H}/{h}\right)\right)^2; \end{aligned} $$

(4)

cf. [7, 8]. If A is not constant, the constant C also depends the contrast of A.

2 Adaptive GDSW in 2D

The adaptive GDSW coarse space is a generalization of the standard GDSW coarse space since the latter is automatically included in the former. To deal with coefficient jumps, additional coarse constraints are added constructed from solving local generalized eigenvalue problems. Let the interface Γ be partitioned into edges ${\mathcal {E}}$ and vertices ${\mathcal {V}}$, i.e., $\varGamma = \left ( \cup _{e \in {\mathcal {E}}} e \right ) \cup \left ( \cup _{v \in {\mathcal {V}}} v \right ).$

For each edge e, we define the sets Ω _e and $\hat \varOmega _e$ as depicted in Fig. 1 (left) and the following extension operator:

$$\displaystyle \begin{aligned} w_e : V_{0}^{h}\left(e\right) \rightarrow V_{0}^{h}\left(\varOmega_e\right), \quad v & \mapsto w_e(v) := \left\lbrace \begin{array}{ll} v & \quad \mbox{in all interior nodes of } e, \\ 0 & \quad \mbox{on all other nodes in } \varOmega_e, \end{array} \right. \end{aligned} $$

where $V_{0}^{h} \left (e\right ) := \left \lbrace \left . v\right |{ }_{e} : v \in V, v = 0 \mbox{ on } \partial e \right \rbrace$. Then, we consider on each edge $e \in {\mathcal {E}}$ the generalized eigenvalue problem: find $\tau _{*,e} \in V_{0}^{h} \left (e\right )$ such that

$$\displaystyle \begin{aligned} {a_{\hat \varOmega_e} \left( {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e} (\tau_{*,e})} , {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e} (\theta)} \right) } = \lambda_{*,e}\; {a_{\varOmega_e} \left( {w_e(\tau_{*,e})} , {w_e(\theta)} \right) } \quad \forall \theta \in V_{0}^{h}\left(e\right). \end{aligned} $$

(5)

Here, $\mathcal {H}_{\hat e \rightarrow \hat \varOmega _e}$ is the discrete harmonic extension from the interior edge $\hat e$ into $\hat \varOmega _e$ with respect to ${a_{\hat \varOmega _e} \left ( {\cdot } , {\cdot } \right ) }$. Let the corresponding eigenvalues be sorted non-descendingly, i.e., λ _1,e ≤ λ _2,e ≤… ≤ λ _m,e (eigenmodes accordingly) where $m = \dim \left (V_{0}^{h}\left (e\right )\right )$. We select all eigenmodes τ _∗,e where the eigenvalues are below $tol_{\mathcal {E}}$, i.e., $\lambda _{*,e} \leq tol_{\mathcal {E}}$. Then we extend the selected eigenfunctions by zero to Γ ∖ e, denoted by $\tilde {\tau }_{*,e}$, and subsequently compute the discrete harmonic extension into the interior of the subdomains, i.e., $v_{*,e}:=\mathcal {H}_{\varGamma \to \varOmega }(\tilde {\tau }_{*,e})$. Note that for every edge e, the left hand side of the eigenvalue problem (5) is singular. Therefore, since $tol_{\mathcal {E}} \geq 0$, eigenmodes which span the nullspace are always selected and added to the coarse space. As a consequence, the standard GDSW coarse space is always included. Additionally, we use the nodal coarse basis functions from the GDSW coarse space, which span the space $V_{\mathrm {\mathcal {V}}}$. The result is the AGDSW (Adaptive GDSW) coarse space:

$$\displaystyle \begin{aligned} \begin{aligned} V_{\mathrm AGDSW}^{tol_{\mathcal{E}}} = V_{\mathrm {\mathcal{V}}} \oplus \left( \oplus _{e \in {\mathcal{E}}} \operatorname*{\mbox{span}} \left\lbrace v_{k,e} : \lambda_{k,e} \leq tol_{\mathcal{E}} \right\rbrace \right) \end{aligned} \end{aligned}$$

Fig. 1

(Left) Graphical representation of Ω _e = Ω _i ∪ Ω _j and $\hat \varOmega _e$. The set $\hat \varOmega _e$ is obtained by removing from Ω _e all elements which are adjacent to the coarse nodes. From this, we also obtain the interior edge $\hat e := e \cap \hat \varOmega _e$. (Right) Graphical representation of the slab $\hat \varOmega _e^l$ corresponding to the edge e

Remark 1

For $tol_{\mathcal {E}} \geq 0$, we obtain $V_{\mathrm GDSW} = V_{\mathrm AGDSW}^{0} \subseteq V_{\mathrm AGDSW}^{tol_{\mathcal {E}}}$.

Remark 2

The right hand side of the eigenvalue problem (5) can be extracted from the fully assembled global stiffness matrix K.

Remark 3

The condition number of the AGDSW Schwarz operator is bounded by

$$\displaystyle \begin{aligned} \kappa\left( M_{\mathrm AGDSW}^{-1} K \right) \leq C \left( 1 + {1}/{tol_{\mathcal{E}}} \right); {} \end{aligned} $$

(6)

see [16]. The constant C is independent of H, h, and the contrast of A.

The threshold ${tol_{\mathcal {E}}}$ used for the selection of the eigenfunctions also controls the condition number (6). In practice, the best choice for ${tol_{\mathcal {E}}}$ exactly separates the eigenvalues corresponding to coefficient jumps from the rest of the spectrum.

2.1 Variants of Adaptive GDSW

Here, we will briefly discuss some possible variants of the AGDSW method.

Mass Matrix

As in other adaptive coarse spaces where a spectral estimate is used to replace a Poincaré type inequality, cf., e.g., [9, 11, 12, 15], we can use a (scaled) mass matrix on the right hand side of the eigenvalue problems. The scaled mass matrix corresponding to an edge $e \subset (\bar \varOmega _i \cap \bar \varOmega _j)$ arises from the discretization of the scaled L ²-inner product

$$\displaystyle \begin{aligned} b_{e} \left( {u} , {v} \right) := \frac{1}{h^2}(A\cdot w_e(u),w_e(v))_{L^2(\varOmega_e)}. \end{aligned} $$

(7)

Therefore, we obtain for each edge the modified generalized eigenvalue problem: find $\tau _{*,e} \in V_{0}^{h} \left (e\right )$ such that

$$\displaystyle \begin{aligned} {a_{\hat \varOmega_e} \left( {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e} (\tau_{*,e})} , {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e} (\theta)} \right) } = \lambda_{*,e} b_{e} \left( {\tau_{*,e}} , {\theta} \right) \quad \forall \theta \in V_{0}^{h}\left(e\right). \end{aligned} $$

(8)

The condition number bound (6) can also be proven for this variant; see [16].

Slabs

Solving the eigenvalue problems can be expensive; they are, however, local and only defined on the interface; moreover, an approximation of the eigenvalues is sufficient; the dimension of the coarse space is relatively small since connected components within subdomains are detected by using Schur complements. We now also introduce a slab variant that allows us to control the computational cost of constructing the generalized eigenvalue problems. Therefore, the set $\hat \varOmega _e$ can be replaced by a slab of width l elements around the edge e in (5); cf. Fig. 1 (right) for the graphical representation of a slab corresponding to the edge e. We denote the slab by $\hat \varOmega _e^{l}$. This idea, to use slabs in the eigenvalue problems, has already been introduced in [15] for related multiscale coarse spaces based on the ACMS space and is also common in FETI-DP and BDDC domain decomposition methods with adaptive coarse spaces.

The modified generalized eigenvalue problem reads: find $\tau _{*,e} \in V_{0}^{h} \left (e\right )$ such that

$$\displaystyle \begin{aligned} {a_{\hat \varOmega_e^l} \left( {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e^l} (\tau_{*,e})} , {\mathcal{H}_{\hat e \rightarrow \hat \varOmega_e^l} (\theta)} \right) } = \lambda_{*,e} {a_{\varOmega_e} \left( {w_e(\tau_{*,e})} , {w_e(\theta)} \right) } \quad \forall \theta \in V_{0}^{h}\left(e\right). \end{aligned} $$

(9)

The slab variant is computationally cheaper and the bound can be proven analogously to the standard version with no modifications. However, the coarse space dimension can increase due to the use of this variant (if $\hat \varOmega _e^l \subset \hat \varOmega _e$).

3 Numerical Results

We present numerical results for model problem (1) for f ≡ 1 and various coefficient functions, comparing the different AGDSW approaches with the standard GDSW as well as the SHEM coarse space, recently introduced by Gander, Loneland, and Rahman in [12]. Finally, we show results using slabs of varying widths.

In all figures, the light and dark blue colors correspond to the minimum ($A_{\min }=1.0$) and maximum coefficient ($A_{\max }=10^6$ or $A_{\max }=10^8$), respectively. We use piecewise bilinear finite elements, and solve the discrete linear system using the conjugate gradient method with a relative stopping criterion ||r ^(k)||₂∕||r ⁽⁰⁾||₂ ≤ 10⁻⁸, where r ⁽⁰⁾ and r ^(k) are the initial and the kth unpreconditioned residual, respectively. By V _GDSW, we denote the standard GDSW space and by ${V^{tol}_{\mathrm {AGDSW}}}$ the new adaptive GDSW coarse space. The variant which uses a scaled mass matrix in the right hand side of the eigenvalue problem, cf. Sect. 2.1 is denoted by ${V^{tol}_{\mathrm {AGDSW-M}}}$, the variant using a slab of width w = lh is denoted by ${V^{tol}_{{\mathrm {AGDSW-E}}({l})}}$, and the SHEM coarse space by ${V^{tol}_{\mathrm {SHEM}}}$; cf. [12].

In Table 1, we compare the different coarse spaces for the two coefficient functions illustrated in Fig. 2. For the coefficient function from Fig. 2 (left), the GDSW coarse space is not sufficient for fast convergence; see Table 1 (left). This is due to multiple disconnected, high coefficient channels and inclusions intersecting the interface. However, the GDSW coarse space is sufficient for the coefficient function from Fig. 2 (right); see Table 1 (right). Here, only one connected high coefficient component exists per edge, all other high coefficient components are entirely contained in the overlap. Let us remark that a reduction of the overlap to one element, i.e., δ = 1h, and using only the standard GDSW coarse space leads to 207 iterations and a condition number of 8.97 × 10⁷. In Table 1, all adaptive methods achieve low condition numbers and converge in few iterations for both coefficient functions. For the coefficient function from Fig. 2 (left), both adaptive GDSW coarse spaces have higher coarse space dimensions compared to the SHEM coarse spaces. This can be explained as follows: first, the entire GDSW coarse space is always included in the AGDSW coarse space and second, all high coefficient components intersecting the interface are disconnected. For the coefficient function from Fig. 2 (right), many channels of high coefficients intersecting the interface are connected. Here, the coarse space ${V^{10^{-6}}_{\mathrm {SHEM}}}$ has a dimension of 213, where both AGDSW approaches have a lower coarse space dimension of 57 using a tolerance of 10⁻².

Fig. 2

Discontinuous coefficient functions A with different types of channels and inclusions intersecting the interface. Maximum coefficient (dark blue color): $A_{ \max }=10^6$ (left), $A_{ \max }=10^8$ (right); 1∕H = 4; H∕h = 30 (left); H∕h = 40 (right); δ = 2h

Table 1 Results for the coefficient functions in Fig. 2: tolerance for the selection of the eigenfunctions, iterations counts, condition numbers, and resulting coarse space dimension for different coarse space variants; 1∕H = 4, H∕h = 30 (left), H∕h = 40 (right), and δ = 2h; maximum coefficient $A_{ \max } = 10^{6}$ (left) and $A_{ \max } = 10^{8}$ (right)

In Fig. 3 (left), we have a randomly generated coefficient function, constructed as follows: uniformly distributed numbers are randomly generated in the interval [0, 1]. A value above 0.6 corresponds to a high coefficient $A_{\max } = 10^{6}$ in a finite element. Otherwise the coefficient is set to $A_{\min }=1.0$. The coefficient of an element touching the global domain boundary is always set to $A_{\min }$. Averaged results for 100 random coefficient functions are listed in Table 2 (left). These results show that all adaptive coarse spaces (AGDSW and SHEM) yield low condition numbers and numbers of iterations. On average, compared to the SHEM coarse space the adaptive GDSW approaches have lower coarse space dimensions. For example, ${V^{10^{-6}}_{\mathrm {SHEM}}}$ and ${V^{10^{-2}}_{\mathrm {AGDSW}}}$ converge in approximately the same number of iterations, i.e., 80.1 and 78.9, respectively. However, ${V^{10^{-6}}_{\mathrm {SHEM}}}$ has a coarse space dimension of 189.2, whereas the dimension of ${V^{10^{-2}}_{\mathrm {AGDSW}}}$ is 127.7. This corresponds to a reduction by 33%.

Fig. 3

(Left) Sample random coefficient function with a density of approximately 40% high coefficients $A_{ \max }=10^6$ (dark blue color). 1∕H = 4; H∕h = 40; δ = 1h. (Right) Detailed view of a coefficient function with $A_{ \max }=10^8$ (dark blue color) and 1∕H = 20, H∕h = 40, δ = 1h

Table 2 Results for the coefficient functions in Fig. 3: tolerance for the selection of the eigenfunctions, iteration counts, condition numbers, and resulting coarse space dimension for different coarse space variants

We also consider a foam-like coefficient function, as depicted in Fig. 3 (right). The results in Table 2 (right) show that a robust preconditioner, with additional coarse constraints, is needed as V _GDSW requires over 3000 iterations to converge. The adaptive GDSW variants and ${V^{ }_{\mathrm {SHEM}}}$ need few iterations to converge. However, ${V^{10^{-4}}_{\mathrm {SHEM}}}$ requires a much larger coarse space, of dimension 4324, compared to ${V^{5\cdot 10^{-2}}_{\mathrm {AGDSW}}}$, dimension 2257, while requiring approximately the same number of iterations to converge. This corresponds to a reduction by 48%.

We now investigate the use of different slab widths in the variant ${V^{ }_{{\mathrm {AGDSW-E}}({l})}}$; cf. Sect. 2.1. We are able to reduce the computational cost by using small slabs. However, this may enlarge the coarse space. This can be observed clearly for the coefficient function in Fig. 4. Increasing the slab width decreases the resulting coarse space dimension for ${V^{ }_{{\mathrm {AGDSW-E}}({l})}}$; also cf. Table 3. In this particular example, a slab width of 13 is sufficient to achieve the same result as with the maximum slab width of 42 since the slab then contains only two high coefficient components per edge.

Fig. 4

Coefficient function with many connected channels intersecting the interface. Maximum coefficient $A_{ \max }=10^6$ (dark blue); 1∕H = 2; H∕h = 42; δ = 2h

Table 3 Results for the coefficient function in Fig. 4: slab width, iterations counts, condition numbers, and resulting coarse space dimension for different coarse space variants