# 77. Additive Schwarz Methods#

In this lecture

we define additive and multiplicative sub-space correction methods

prove the Additive Schwarz Lemma as tool for the analysis of additive Schwarz methods

The method is named after Hermann Schwarz, who used this technique for proving the existence of solutions of PDEs.

Literature: Xu, Jinchao: Iterative methods by space decomposition and subspace correction. *SIAM Rev.* 34 (1992), no. 4, 581–613
https://epubs.siam.org/doi/10.1137/1034116

## 77.1. Block-Jacobi and general additive Schwarz preconditioners#

Let \(e_i\) be the \(i^{th}\) unit vector. The diagonal entry of the matrix \(A\) is \(a_{ii} = e_i^T A e_i\). We can represent the Jacobi-preconditioner as

A block-Jacobi preconditioner is

where we have \(m\) diagonal blocks, of sizes \(N_i\).

For \(i = 1 \ldots m\) we define embedding matrices \(E_i\) consisting of the unit-vectors corresponding to the \(i^{th}\) block:

We can write the diagonal blocks as

and the whole Block-Jacobi preconditioner as

and the preconditioning action

Next, we let the \(E_i\) be more general full rank, typically tall rectangular matrices. Let \(A_{i} = E_i^T A E_i \in {\mathbb R}^{N_i}\). Then we call the preconditioner defined by the action

an additive Schwarz preconditioner \(C_{ASM}\). In general we don’t have the simple representation as for the block-Jacobi preconditioner for \(C_{ASM}\) itself.

The action

can be split into the following steps:

\(\qquad\) \(r_i = E_i^T r \qquad\) extract residual on sub-space

\(\qquad\) \(w_i = A_{i}^{-1}r_i \qquad\) solve problem on sub-space

\(\qquad\) \(w = \sum_{i=1}^m E_i w_i \qquad\) embed and combine sub-space solution

## 77.2. Sub-spaces of \({\mathbb R}^N\) and of Hilbert-spaces#

The definition and implementation of the ASM - preconditioner happens in linear algebra, i.e. in \({\mathbb R}^N\). But for the analysis of the preconditioner we reformulate it in finite element space \(V_h\) and sub-spaces.

We define the so called Galerkin isomorphismus

Every finite element function \(u_h\) can be identified with its coefficient vector \(\underline u\) with respect to the basis functions \(\{\varphi_i\}\).

For \(\underline u, \underline v \in {\mathbb R}^N\), there holds

where \(A\) is the Galerkin discretization matrix with entries \(A_{ji} = A(\varphi_i, \varphi_j)\).

The adjoint of the Galerkin isomorphism is a mapping from the dual of \(V_h\), i.e. from the linear forms on \(V_h\), into \({\mathbb R}^N\):

The embedding matrices \(E_i \subset {\mathbb R}^{N \times N_i}\) define sub-spaces

The ASM preconditioner can be reformulated by means of variational problems on sub-spaces:

Lemma: Let \(r(.) \in V_h^\ast\). Then\[ w = G C_{ASM}^{-1} G^* r \; \; \in V_h \]is given as

\[ w = \sum_{i=1}^m w_i \quad \text{with} \quad w_i \in V_i : A(w_i,v_i) = r(v_i) \; \forall \, v_i \in V_i \]

*Proof:* Express \(w_i = G E_i \underline w_i\) and \(v_i = G E_i \underline v_i\) with \(\underline w_i, \underline v_i \in {\mathbb R}^{N_i}\). Then the defining equation of \(w_i\) reads as

and thus as

i.e. \(w_i = A_i^{-1} E_i^T (G^* r)\).

Finally, \(w = \sum w_i = \sum G E_i \underline w_i = G \sum E_i \underline w_i = G \sum E_i A_i^{-1} E_i^T (G^* r)\).

**Lemma** Let \(\underline{w}_i = E_i A_{i}^{-1} E_i^T A \underline{v}\), and \(w_i = G E_i \underline{w}_i\) and \(v = G \underline v\). Then

with \(P_i\) the \(A(.,.)\) orthogonal projector onto \(V_i\):

*Proof:* Follows from the proof of the Lemma above using \(r(\cdot) = A(v,\cdot)\).

**Lemma:** There holds

This implies that the condition number \(\kappa_A \{C_{ASM}^{-1} A\}\) equals \(\kappa_A \{ \sum P_i \}\). The ideal case is that all sub-spaces are \(A\)-orthogonal, then \(\sum P_i = Id\).

**Lemma:** For the error propagation matrix there holds

A block-Gauss-Seidel iteration leads to the so called multiplicative Schwarz preconditioner, with the error propagation operator

As a product of \(A\)-orthogonal projectors it has \(||M_{MSM}||_A \leq 1\). Its \(\left<.,.\right>_A\)-adjoint is the product in reverse ordering.

## 77.3. The Additive Schwarz Lemma#

We have defined the action of the ASM preconditioner. To analyze the condition number via bounds of the Rayleigh quotient

it is of useful to have an representation of the quadratic form generated by \(C_{ASM}\) itself. This is given by the *Additive Schwarz Lemma*. Since it was reformulated and reproven by many authors it is also called *Lemma of many parents*. In some variants it is also know as Lions’s Lemma, or fictitious space lemma by Nepomnyashchikh.

We assume that \(E_i\) are embedding matrices as above such that

This means that every \(u \in {\mathbb R}^N\) can be decomposed into vectors in the range of \(E_i\), not necessarily unique.

Theorem:ASM-lemma, Linear Algebra version:For all \(u \in {\mathbb R}^N\) there holds:

\[ u^T C_{ASM} u = \inf_{u_i \in {\mathbb R}^{N_i} \atop u = \sum E_i u_i} \sum_{i=1}^m u_i^T A_{i} u_i \]

TheoremASM-lemma, sub-space version:For all \(u \in V_h\) there holds:

\[ u^T C_{ASM} u = \inf_{u_i \in V_i \atop G u = \sum u_i} \sum_{i=1}^m \| u_i \|_A^2 \]

*Proof:* We prove the version in linear algebra notation, the other follows using the Galerkin isomorphism as above.

Fix \(u \in {\mathbb R}^N\). The form \(u^T C_{ASM} u\) is given as the minimum of the constraint minimization problem

The feasible set is non-empty and convex, and the goal function is convex. Thus, the unique minimizer can be found by the method of Lagrange multipliers. The Lagrange function is

There exists a unique Lagrange multiplier \(\lambda\) such that \(L\) has a stationary point \(((u_i), \lambda)\).

Differentiating \(L\) with respect an individual \(u_i\) we get

and thus

Differentiating with respect to \(\lambda\) we recover the constraint

Inserting leads to

We find the definition of the preconditiong action

Since for every \(u\) there exists a unique \(\lambda\), \(C_{ASM}^{-1}\) is indeed the inverse of a regular matrix \(C_{ASM}\), and we can write

The value of the minimum is

\(\Box\)

## 77.4. The upper-bound by the overlap#

Typically, proving the estimate

is the hard part of the analysis, which has to be shown by explicitly constructing a decomposition. The other estimate often follows immediately from finite overlap of sub-spaces:

We define the overlap matrix \({\mathcal O} \in {\mathbb R}^{m \times m}\) with entries

By the Cauchy-Schwarz inequality there is \(0 \leq {\mathcal O}_{i,j} \leq 1\). The value \({\mathcal O}_{i,j}\) leads to the so called strengthened Cauchy-Schwarz inequality

If two sub-spaces are \(A\)-orthogonal, then \({\mathcal O}_{i,j} = 0\).

LemmaThere holds\[ \| u \|_A^2 \leq \rho({\mathcal O}) \, \| u \|_{C_{ASM}}^2, \]where \(\rho({\mathcal O})\) is the spectral radius of \({\mathcal O}\).

Proof: Let \(u \in V_h\) be given, and let \(u = \sum u_i\) be an arbitrary sub-space decomposition. Then

Next, we define \(z \in {\mathbb R}^N\) as \(z_i = \| u_i \|_A\). We use

to bound

Since the estimate holds for any decomposition, it holds also for the one leading to the minimal right hand side, what is exactly \(\| u \|_{C_{ASM}}^2\).