Complete, Optimal and Optimized Coarse Spaces for Additive Schwarz

Abstract

The additive Schwarz method does not converge in general when used as a stationary iterative method, it must be used as a preconditioner for a Krylov method. In the two level variant of the additive Schwarz method, a coarse grid correction is added to make the method scalable. We introduce a new coarse space for the additive Schwarz method which makes it convergent when used as a stationary iterative method, and show that an optimal choice even makes the method nilpotent, i.e. it converges in one iteration, independently of the overlap and the number of subdomains. We then show how this optimal choice can be approximated leading to a spectral harmonically enriched coarse space, based on interface eigenvalue problems. We present a convergence analysis of our new coarse corrections in the two subdomain case in two spatial dimensions, and also compare them with GenEO recently proposed by Spillane, Dolean, Hauret, Nataf, Pechstein, and Scheichl, and the local spectral multiscale coarse space proposed by Galvis and Efendiev.

1 Introduction and Model Problem

Coarse spaces are needed to achieve scalability in domain decomposition methods, see [16] and references therein. More recently, new coarse corrections were also designed to improve convergence, for example in high contrast problems. Such enriched coarse spaces were first proposed in [4, 5], where volume eigenfunctions were combined with different types of partition of unity functions, and further developed in [3]. A coarse space using the eigenfunctions of the Dirichlet-to-Neumann maps on the boundary of each subdomain has been proposed and analyzed in [2, 13], and further development led to solving a generalized eigenvalue problem in the overlap (GenEO), see [14, 15].

A new, different idea is to first define an optimal coarse space, which leads to the best possible convergence and makes the method nilpotent [7]¹ and then to approximate it [8, 10,11,12]. Following this principle, we design here for the first time an optimal coarse space for the additive Schwarz (AS) method with arbitrary sized overlaps, and then define an optimized approximation using a specific function in the overlap, combined with harmonic extensions of interface eigenfunctions. We compare our new coarse space to the GenEO coarse space [14, 15] and the local spectral multiscale coarse space (also with reduced energy) in [4].

Determining an optimal coarse space and then approximating it is a very general idea, see for example the SHEM coarse space [8, 12], but for simplicity we consider here

$$\displaystyle \begin{aligned} \varDelta u = f \quad \text{in}\\varOmega,\qquad u = 0 \quad \text{on}\\partial \varOmega, \end{aligned} $$

(1)

where Ω := (0, 1) × (0, γ) is decomposed into two overlapping subdomains Ω ₁ := (0, β) × (0, γ) and Ω ₂ := (α, 1) × (0, γ), with overlap Ω _o := Ω ₁ ∩ Ω ₂, and interfaces Γ ₁ := {(x, y)|x = β, 0 < y < γ} and Γ ₂ := {(x, y)|x = α, 0 < y < γ}, which leads to the partition of the domain $\bar {\varOmega }=\bar {\tilde {\varOmega }}_1 \cup \bar {\varOmega }_o \cup \bar {\tilde {\varOmega }}_2$; see Fig. 1.

Fig. 1

Continuous (left) and discrete (right) partition of Ω into two overlapping subdomains

Discretizing (1) by the classical five-point finite difference scheme, we obtain the linear system A u = f. Starting with an initial guess u ⁰, the iterative two level additive Schwarz method with multiplicative (hybrid) coarse grid correction computes

$$\displaystyle \begin{aligned} \begin{aligned} {\mathbf{u}}^{n-1/2} &= {\mathbf{u}}^{n-1} + (R_1^{T}A_1^{-1}R_1 + R_2^{T}A_2^{-1}R_2)(\mathbf{f} - A {\mathbf{u}}^{n-1}),\\ {\mathbf{u}}^{n} &= {\mathbf{u}}^{n-1/2} + R_c^{T}A_c^{-1}R_c (\mathbf{f} - A {\mathbf{u}}^{n-1/2}), \end{aligned} \end{aligned} $$

(2)

where R _i are rectangular restriction matrices corresponding to Ω _i, $A_i = R_i A R_i^{T}$, i = 1, 2, and R _c is a restriction matrix to a coarse space, $A_c = R_c A R_c^{T}$.

2 Complete, Optimal and Optimized Coarse Spaces

Definition 1 (Complete Coarse Space)

A complete coarse space for the additive Schwarz method (2) is given by R _c such that (2) converges after one iteration for an arbitrary initial guess u ⁰, i.e. the method is nilpotent and becomes a direct solver.

To give an example of a complete coarse space, and being able to write discrete problems using the same notation as continuous ones, we denote by Δ _h the discretized Laplacian, and by Ω _h, Ω _ih, $\tilde {\varOmega }_{ih}$ Ω _oh, Γ _ih the corresponding discretized spaces, i = 1, 2. Let $N_{\varGamma _{i}}$ be the number of degrees of freedom (DOFs) on the interface Γ _ih, i = 1, 2, and let $\mathbf {\phi }_{i,\mathrm {cs}}^j$ be defined for each DOF on Γ _ih by harmonic extension,

$$\displaystyle \begin{aligned} \begin{aligned} \varDelta_h \mathbf{\phi}_{i,\mathrm{cs}}^{j} &= 0 \; &&\text{in}\\tilde{\varOmega}_{ih},\\ \mathbf{\phi}_{i,\mathrm{cs}}^{j} &= 1 \; && \text{at}\\text{DOF}\j\\text{of}~\varGamma_{3-i,h},\ j=1,\ldots,N_{\varGamma_{3-i}},\\ \mathbf{\phi}_{i,\mathrm{cs}}^{j} &= 0 \; && \text{elsewhere}\\text{in}\\varOmega_h. \end{aligned} \end{aligned} $$

(3)

Denoting by N _o the number of DOFs in the overlap Ω _oh, we define for each of them the further basis function $\mathbf {\phi }_{o,\mathrm {cs}}^j =1$, extended by zero to the rest of Ω _h, j = 1, …, N _o, and

$$\displaystyle \begin{aligned} V_{0,\mathrm{cs}}:= \text{span} \{\{\{\mathbf{\phi}_{i,\mathrm{cs}}^j\}_{j=1}^{N_{\varGamma_{3-i}}}\}_{i=1}^{2} \cup \{\mathbf{\phi}_{o,\mathrm{cs}}^j\}_{j=1}^{N_o}\}. \end{aligned} $$

(4)

Theorem 1

A complete coarse space for the iterative two level additive Schwarz algorithm (2) is given by R _c containing in its columns the vectors of V _0,cs from (4).

Proof

The proof is technical, see [9], but the property is illustrated in Sect. 4.

The dimension of this complete coarse space depends on the number of DOFs in the overlap for AS which was designed to be symmetric [6], but it can be reduced.²

Definition 2 (Optimal Coarse Space)

An optimal coarse space for (2) is a complete coarse space such that its associated R _c has the smallest number of columns possible.

For an optimal coarse space, we define the restriction matrix in the overlap, $R_o:=[0 \quad I_{\varOmega _{oh}} \quad 0]$, where $I_{\varOmega _o}$ is the identity matrix whose dimension equals the number of unknowns in Ω _oh, and the associated local solver in the overlap, $A_o:= R_o AR_o^T$. We then construct just one specific basis function ϕ _o in the overlap Ω _oh for (2), based on the initial guess u ⁰ by solving

$$\displaystyle \begin{aligned} A_o \mathbf{\phi}_o = R_o (\mathbf{f} - A{\mathbf{u}}^0), \end{aligned}$$

and then extending ϕ _o with zero to the rest of Ω _h. We also need the basis functions $\mathbf {\phi }_{i,\mathrm {opt}}^j$, $j=1,\ldots ,N_{\varGamma _{3-i}}, i=1,2$, based on harmonic extensions,

$$\displaystyle \begin{aligned} \begin{array}{rlllrlll} \varDelta_h \mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 0 \; &&\text{in} \;\tilde{\varOmega}_{ih}, & \varDelta_h \mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 0 &&\text{in} \; \varOmega_{oh},\\ \mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 1 \; && \text{at}\\text{DOF}\j\\text{of}\\varGamma_{3-i,h}, &\mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 1 \; && \text{at}\\text{DOF}\j\\text{of}\\varGamma_{3-i,h},\\ \mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 0 \; && \text{elsewhere}\\text{in}\\varOmega_h, &\mathbf{\phi}_{i,\mathrm{opt}}^{j} &= 0 \; && \text{elsewhere}\\text{in}\\varOmega_h, \end{array} \end{aligned}$$

and define

$$\displaystyle \begin{aligned} V_{0,\mathrm{opt}}:= \text{span} \{\{\{\mathbf{\phi}_{i,\mathrm{opt}}^j\}_{j=1}^{N_{\varGamma_{3-i}}}\}_{i=1}^{2} \cup \{\mathbf{\phi}_{o}\} \}. \end{aligned} $$

(5)

Theorem 2

An optimal coarse space for the iterative two level additive Schwarz algorithm (2) is given by R _c containing in its columns the vectors of V _0,opt from (5).

Proof

The proof is given in [9], but the property is again illustrated in Sect. 4.

At the continuous level, even the optimal coarse space would still be infinite dimensional, and we thus introduce now an approximation of the optimal coarse space based on SHEM (Spectral Harmonically Enriched Multiscale coarse space [8]) using an interface eigenvalue problem:

Definition 3 (Interface Eigenvalue Problem)

Denoting by D _yy an approximation of the second derivative along the interface Γ _i, the interface eigenvalue problem is

$$\displaystyle \begin{aligned} - D_{yy} \mathbf{\psi}_{i} = \lambda \mathbf{\psi}_i \quad \text{on}\\varGamma_{ih}, \end{aligned} $$

(6)

with zero Dirichlet boundary conditions ψ _i(0) = ψ _i(γ) = 0, i = 1, 2.

In our example, the eigenvectors of the interface eigenvalue problem (6) are $\mathbf {\psi }_i^j=\sin {}((j \pi /\gamma ) y_m)$, y _m = mh. We can thus construct basis functions $\mathbf {\phi }_{i,\mathrm {app}}^j$ by the harmonic extensions of the sine functions for i = 1, 2,

$$\displaystyle \begin{aligned} \begin{array}{rlllrlll} \varDelta_h \mathbf{\phi}_{i,\mathrm{app}}^{j} &= 0 && \text{in}\\tilde{\varOmega}_{ih}, & \varDelta_h \mathbf{\phi}_{i,\mathrm{app}}^{j} &= 0 && \text{in}\\varOmega_{oh},\\ \mathbf{\phi}_{i,\mathrm{app}}^{j} &= \mathbf{\psi}_{3-i}^j && \text{on}\\varGamma_{3-i,h}, & \mathbf{\phi}_{i,\mathrm{app}}^{j} &= \mathbf{\psi}_{3-i}^j && \text{on}\\varGamma_{3-i,h}\\ \mathbf{\phi}_{i,\mathrm{app}}^{j} &= 0 \; && \text{elsewhere}\\text{in}\\varOmega_h, &\mathbf{\phi}_{i,\mathrm{app}}^{j} &= 0 \; && \text{elsewhere}\\text{in}\\varOmega_h, \end{array} \end{aligned} $$

(7)

j = 1, …, ℓ, where ℓ is the number of the eigenvectors of the interface eigenvalue problem (6) selected; see Fig. 2 for an illustration. We then define an optimized approximation of the optimal coarse space

$$\displaystyle \begin{aligned} V_{0,\mathrm{cs-l}} = \text{span} \{\{\{\mathbf{\phi}_{i,\mathrm{app}}^j\}_{j=1}^{\ell}\}_{i=1}^{2} \cup \{\mathbf{\phi}_{o}\} \}. \end{aligned} $$

(8)

Fig. 2

First three basis functions used to approximate the optimal coarse space based on the interface eigenfunctions, and the single mode in the overlap for a random initial guess on the right

Theorem 3

The iterative two level additive Schwarz algorithm (2) with R _c containing in its columns the vectors of V _0,cs−l in (8) satisfies the error estimate

and there is no other coarse space of this dimension that leads to faster convergence.

Proof

The proof can be obtained by a direct calculation using separation of variables for the residual after one additive Schwarz iteration, and will be given in [9].

3 Comparison to Two Other Coarse Spaces

We now compare our optimized coarse space to the GenEO coarse space from [14, 15], and the local spectral multiscale coarse space with reduced energy from [4]. The GenEO coarse space was designed for high contrast problems and is based on generalized eigenproblems “in the overlap”: in our example it solves in Ω _i, i = 1, 2,

$$\displaystyle \begin{aligned} \hat{A}_i {\mathbf{p}}_i^j = \lambda_i^j X_i \hat{A}_i^o X_i {\mathbf{p}}_i^j \end{aligned} $$

(9)

for eigenvectors ${\mathbf {p}}_i^j \in \mathbb {R}^{\#\overline {\text{dof}}(\varOmega _i)}$ assoicated with small eigenvalues $\lambda _i^j \in \mathbb {R} \bigcup \{+\infty \}$. In (9), X _j is a diagonal matrix indicating the partition of unity used to combine subdomain solutions, and $\hat {A}_i$, $\hat {A}_i^o$ are Neumann matrices for each subdomain. Selecting the ℓ eigenfunctions corresponding to the smallest eigenvalues then leads to the GenEO coarse space

$$\displaystyle \begin{aligned} V_{0,\mathrm{GenEO}} = \text{span} \{R_i^TX_i {\mathbf{p}}_i^j, j = 1,\dots, \ell,\; i=1,2\}. \end{aligned}$$

To understand how GenEO is related to our optimized coarse space, we first rewrite the eigenvalue problem (9) at the continuous level for λ _i ≠ 0 and λ _i ≠ 4,

$$\displaystyle \begin{aligned} \begin{array}{rlllrlll} \varDelta \hat{p}_i (x,y) &= 0 & &\text{in}~\hat{\tilde{\varOmega}}_i, & \varDelta p_{io}(x,y) &= 0 & &\text{in}~\varOmega_o,\\ \hat{p}_i &= p_{io} &&\text{on}~\hat{\varGamma}_{3-i}, & p_{io} &= \dfrac{4}{4-\lambda_i}\hat{p}_i & &\text{on}~\varGamma_{3-i}, \end{array} \end{aligned} $$

(10)

with boundary conditions $\hat {p}_i = 0$ on $\partial \varOmega \cap \bar {\hat {\tilde {\varOmega }}}_i$, p _io = 0 on $(\partial \varOmega \cap \bar {\hat {\tilde {\varOmega }}}_o) \backslash \varGamma _{i}$ and ∂ _n p _io = 0 on Γ _i, and then define $p_i:=\hat {p}_i$ in $\hat {\tilde {\varOmega }}_i$, p _i := p _io in Ω _o, and p _i := 0 in the rest of Ω, i = 1, 2. Here, $\varGamma _i^{\prime }$ are within one mesh size from the corresponding boundary Γ _i, i = 1, 2, see Fig. 3 on the left. Solving (10) with separation of variables for Ω ₁, we find for our model problem

$$\displaystyle \begin{aligned} \begin{aligned} p_1^j(x,y) &= \begin{cases} \dfrac{4}{4-\lambda_1^j} \dfrac{\sinh(\frac{j\pi}{\gamma} x)} {\sinh(\frac{j\pi}{\gamma}\alpha')} \dfrac{\cosh(\frac{j\pi}{\gamma}(\beta-\alpha'))} {\cosh(\frac{j\pi}{\gamma}(\beta-\alpha))}\sin{}(\frac{j\pi}{\gamma}y) , & (x,y) \in(0,\alpha)\times (0,\gamma),\\ \dfrac{4}{4-\lambda_1^j} \dfrac{\cosh(\frac{j\pi}{\gamma}(\beta-x))} {\cosh(\frac{j\pi}{\gamma}(\beta-\alpha))} \sin{}(\frac{j\pi}{\gamma}y), & (x,y) \in (\alpha,\beta) \times (0,\gamma), \end{cases}\\ \lambda_1^j &= 4 - 4 \dfrac{\sinh(\frac{j\pi}{\gamma} \alpha)} {\sinh(\frac{j\pi}{\gamma}\alpha')} \dfrac{\cosh(\frac{j\pi}{\gamma}(\beta-\alpha '))} {\cosh(\frac{j\pi}{\gamma}(\beta-\alpha))}. \end{aligned} \end{aligned}$$

We show in Fig. 4 the three types of GenEO eigenfunctions. The eigenfunctions corresponding to the smallest eigenvalues are like the ones in our optimized coarse space within the subdomains, but in the overlap they differ. Since GenEO uses an eigenvalue problem in the entire subdomain volume, it also contains many more eigenfunctions (which one avoids to compute in GenEO), like the overlap ones for λ = 4 corresponding to $\mathbf {\phi }_{o,\mathrm {cs}}^j$ in our complete coarse space, plus the ones for λ = ∞ which do not contain relevant information for the coarse space.

Fig. 3

Left: partition of the domain for the GenEO coarse space. Right: partition of the domain for the local multiscale coarse space with reduced energy

Fig. 4

First three basis functions on Ω ₁ of the eigenvalue problem from GenEO for the smallest λ, followed by 3 of the randomly looking modes for λ = 4 and 2 of the modes for λ = ∞

We next compare our optimized coarse space with the local spectral multiscale coarse space (also with reduced energy) in [4]. The domain Ω is still decomposed into two overlapping subdomains Ω ₁ and Ω ₂, with six coarse blocks K _i, i = 1, …, 6, see Fig. 3 on the right. Let ${\mathbf {q}}_i^j$ denote the jth eigenvector of the volume eigenvalue problem in subdomain Ω _ih, i = 1, 2,

$$\displaystyle \begin{aligned} \begin{aligned} \varDelta_h {\mathbf{q}}_i &= \lambda_i {\mathbf{q}}_i \quad && \text{in}\\varOmega_{ih},\\ \partial_n {\mathbf{q}}_i &= 0 \quad && \text{on}\\varGamma_{ih},\\ {\mathbf{q}}_i&=0 \quad &&\text{on}\\partial \varOmega_{ih} \backslash \varGamma_{ih}. \end{aligned}\end{aligned} $$

(11)

With the partition of unity χ _i, i = 1, 2, the local spectral multiscale coarse space of [4] using ℓ functions is defined by

$$\displaystyle \begin{aligned} V_{0,\mathrm{mul}} = \text{span} \{ R_i^T\chi_i {\mathbf{q}}_i^j, 1\leq j \leq \ell ,i=1,2\}.\end{aligned} $$

(12)

The local spectral multiscale coarse space with reduced energy of [4] is defined by

$$\displaystyle \begin{aligned} \tilde{V}_{0,\mathrm{mul}} = \text{span} \{ R_i^T \tilde{\mathbf{q}}_i^j, 1\leq j \leq \ell, i=1,2\},\end{aligned} $$

where for each block K _h ∈ Ω _ih, i = 1, 2, 1 ≤ j ≤ ℓ, one still needs to solve $\varDelta _h \tilde {\mathbf {q}}_i^j = 0$ in K _h, $\tilde {\mathbf {q}}_i^j = \chi _i {\mathbf {q}}_i^j$ on ∂K _h. Solving (11) using separation of variables, we find in Ω ₁

$$\displaystyle \begin{aligned} {\mathbf{q}}_1^{jk}(x,y) = \sin{}(\dfrac{k\pi-\pi/2}{\alpha}x)\sin{}(\dfrac{j\pi}{\gamma}y),\quad \lambda_1^{jk} = (\dfrac{k\pi-\pi/2}{\alpha})^2 + (\dfrac{j\pi}{\gamma})^2.\end{aligned} $$

We show in Fig. 5 the first few of those modes. Note that these modes are different from the modes in our optimized coarse space and GenEO, and again one needs to solve volume eigenvalue problems to construct the coarse spaces V _0,mul and $\tilde {V}_{0,\mathrm {mul}}$, which now also contain many redundant modes.

Fig. 5

Top: First four basis functions of the local spectral multiscale coarse space V _0,mul. Bottom: corresponding modes for the reduced energy case

4 Numerical Experiments

We solve (1) with f = −3 on Ω = (0, 1) × (0, 1) discretized by centered finite differences and using an overlap of 4h, h being the mesh parameter. We start with a random initial guess, and stop the iteration when the error in the iterative method or the residual in PCG reaches the tolerance 1e − 8. In Table 1 we show the dependence of the number of iterations on h for the complete coarse space (CS), the optimal coarse space (CS-opt), our optimized coarse space SHEM(ℓ), and GenEO(ℓ), GalvisI(ℓ) and GalvisII(ℓ) (reduced energy), using ℓ = 3 enrichment functions for each subdomain. We see that CS and CS-opt are direct solvers, and only SHEM(ℓ) leads to a convergent stationary iteration; and SHEM(ℓ) also performs best with PCG.

Table 1 Iteration number comparison in the two subdomain case for different mesh parameters h

In Table 2, we show the iteration numbers for 2 × 2, 4 × 4, and 8 × 8 subdomains using h = 1∕32, 1∕64, 1∕128, i.e. keeping H∕h fixed. We choose again ℓ = 3 for SHEM, and approximately the same total number of coarse functions for the other coarse spaces. We see again that CS and CS-opt are direct solvers, and only SHEM leads to a convergent stationary method. When used with PCG, the methods are all scalable, but SHEM needs only half the number of iterations compared to the other methods.

Table 2 Iteration number comparison for many subdomains