Additive Schwarz Methods

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^{t h}$ unit vector. The diagonal entry of the matrix $A$ is $a_{i i} = e_{i}^{T} A e_{i}$ . We can represent the Jacobi-preconditioner as

C_{J a c}^{- 1} = (diag A)^{- 1} = \sum_{i = 1}^{N} e_{i} \frac{1}{e_{i}^{T} A e_{i}} e_{i}^{T}

A block-Jacobi preconditioner is

\begin{array}{r} C_{b J a c} = (\begin{array}{cccc} A_{11} & 0 & \dots & 0 \\ 0 & A_{22} & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 0 & \dots & 0 & A_{m m} \end{array}), \end{array}

where we have $m$ diagonal blocks, of sizes $N_{i}$ .

For $i = 1 \dots m$ we define embedding matrices $E_{i}$ consisting of the unit-vectors corresponding to the $i^{t h}$ block:

\begin{array}{r} E_{i} = (\begin{array}{c} 0 \\ I_{N_{i}} \\ 0 \end{array}) = (e_{i, 1}, \dots, e_{i, N_{i}}) \in R^{N \times N_{i}} \end{array}

We can write the diagonal blocks as

A_{i i} = E_{i}^{T} A E_{i} \in R^{N_{i} \times N_{i}}

and the whole Block-Jacobi preconditioner as

C_{b J a c} = \sum_{i = 1}^{m} E_{i} A_{i i} E_{i}^{T},

and the preconditioning action

C_{b J a c}^{- 1} = \sum_{i = 1}^{m} E_{i} A_{i i}^{- 1} E_{i}^{T}

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 R^{N_{i}}$ . Then we call the preconditioner defined by the action

C_{A S M}^{- 1} = \sum_{i = 1}^{m} E_{i} A_{i}^{- 1} E_{i}^{T}

an additive Schwarz preconditioner $C_{A S M}$ . In general we don’t have the simple representation as for the block-Jacobi preconditioner for $C_{A S M}$ itself.

The action

C_{A S M}^{- 1} : R^{N} \to R^{N} : r \mapsto w

can be split into the following steps:

$r_{i} = E_{i}^{T} r$ extract residual on sub-space
$w_{i} = A_{i}^{- 1} r_{i}$ solve problem on sub-space
$w = \sum_{i = 1}^{m} E_{i} w_{i}$ embed and combine sub-space solution

77.2. Sub-spaces of $R^{N}$ and of Hilbert-spaces#

The definition and implementation of the ASM - preconditioner happens in linear algebra, i.e. in $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

\begin{array}{rcl} G : R^{N} & \to & V_{h} \\ \underset{―}{u} & \mapsto & u_{h} = \sum_{i = 1}^{N} u_{i} φ_{i} . \end{array}

Every finite element function $u_{h}$ can be identified with its coefficient vector $\underset{―}{u}$ with respect to the basis functions ${φ_{i}}$ .

For $\underset{―}{u}, \underset{―}{v} \in R^{N}$ , there holds

{\underset{―}{v}}^{T} A \underset{―}{u} = A (G \underset{―}{u}, G \underset{―}{v}),

where $A$ is the Galerkin discretization matrix with entries $A_{j i} = A (φ_{i}, φ_{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 $R^{N}$ :

\begin{array}{rcl} G^{*} : V_{h}^{*} & \to & R^{N} \\ r (.) & \mapsto & (r (φ_{i}))_{i = 1 \dots N} \end{array}

The embedding matrices $E_{i} \subset R^{N \times N_{i}}$ define sub-spaces

V_{i} = G range {E_{i}} = {G E \underset{―}{v} : \underset{―}{v} \in R^{N_{i}}} \subset V_{h}

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

Lemma: Let $r (.) \in V_{h}^{*}$ . Then

$w = G C_{A S M}^{- 1} G^{*} r \in V_{h}$

is given as

$w = \sum_{i = 1}^{m} w_{i} with 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} {\underset{―}{w}}_{i}$ and $v_{i} = G E_{i} {\underset{―}{v}}_{i}$ with ${\underset{―}{w}}_{i}, {\underset{―}{v}}_{i} \in R^{N_{i}}$ . Then the defining equation of $w_{i}$ reads as

A (G E_{i} {\underset{―}{w}}_{i}, G E_{i} {\underset{―}{v}}_{i}) = r (G E_{i} {\underset{―}{v}}_{i}) \forall {\underset{―}{v}}_{i} \in R^{N_{i}}

and thus as

{\underset{―}{v}}_{i}^{T} E_{i}^{T} A E_{i} {\underset{―}{w}}_{i} = v_{i}^{T} E_{i}^{T} G^{*} r,

i.e. $w_{i} = A_{i}^{- 1} E_{i}^{T} (G^{*} r)$ .

Finally, $w = \sum w_{i} = \sum G E_{i} {\underset{―}{w}}_{i} = G \sum E_{i} {\underset{―}{w}}_{i} = G \sum E_{i} A_{i}^{- 1} E_{i}^{T} (G^{*} r)$ .

Lemma Let ${\underset{―}{w}}_{i} = E_{i} A_{i}^{- 1} E_{i}^{T} A \underset{―}{v}$ , and $w_{i} = G E_{i} {\underset{―}{w}}_{i}$ and $v = G \underset{―}{v}$ . Then

w_{i} = P_{i} v

with $P_{i}$ the $A (., .)$ orthogonal projector onto $V_{i}$ :

P_{i} : V_{h} \to V_{i} : A (P_{i} v, z) = A (v, z) \forall v \in V_{h}, z \in V_{i}

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

Lemma: There holds

G C_{A S M}^{- 1} A = \sum_{i = 1}^{M} P_{i} G

This implies that the condition number $κ_{A} {C_{A S M}^{- 1} A}$ equals $κ_{A} {\sum P_{i}}$ . The ideal case is that all sub-spaces are $A$ -orthogonal, then $\sum P_{i} = I d$ .

Lemma: For the error propagation matrix there holds

G (I - τ C_{A S M}^{- 1} A) = (I - τ \sum_{i = 1}^{M} P_{i}) G

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

M_{M S M} = (I - P_{m}) \dots (I - P_{2}) (I - P_{1})

As a product of $A$ -orthogonal projectors it has $| | M_{M S M} | |_{A} \leq 1$ . Its ${⟨ ., . ⟩}_{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

γ_{1} \leq \frac{u^{T} A u}{u^{T} C_{A S M} u} \leq γ_{2}

it is of useful to have an representation of the quadratic form generated by $C_{A S M}$ 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

\sum_{i = 1}^{m} range {E_{i}} = R^{N}

This means that every $u \in 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 R^{N}$ there holds:

$u^{T} C_{A S M} u = inf_{\binom{u_{i} \in R^{N_{i}}}{u = \sum E_{i} u_{i}}} \sum_{i = 1}^{m} u_{i}^{T} A_{i} u_{i}$

Theorem ASM-lemma, sub-space version:

For all $u \in V_{h}$ there holds:

$u^{T} C_{A S M} u = inf_{\binom{u_{i} \in V_{i}}{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 R^{N}$ . The form $u^{T} C_{A S M} u$ is given as the minimum of the constraint minimization problem

inf_{\binom{u_{i} \in R^{N_{i}}}{u = \sum E_{i} u_{i}}} \sum_{i = 1}^{m} u_{i}^{T} A_{i} u_{i} .

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

L ((u_{i}), λ) = \sum u_{i}^{T} A_{i} u_{i} + λ^{T} (u - \sum E_{i} u_{i})

There exists a unique Lagrange multiplier $λ$ such that $L$ has a stationary point $((u_{i}), λ)$ .

Differentiating $L$ with respect an individual $u_{i}$ we get

2 A_{i} u_{i} - E_{i}^{T} λ = 0

and thus

u_{i} = \frac{1}{2} A_{i}^{- 1} E_{i}^{T} λ .

Differentiating with respect to $λ$ we recover the constraint

u = \sum_{i} E_{i} u_{i} .

Inserting leads to

u = \frac{1}{2} \sum_{i} E_{i} A_{i}^{- 1} E_{i}^{T} λ

We find the definition of the preconditiong action

u = \frac{1}{2} C_{A S M}^{- 1} λ

Since for every $u$ there exists a unique $λ$ , $C_{A S M}^{- 1}$ is indeed the inverse of a regular matrix $C_{A S M}$ , and we can write

λ = 2 C_{A S M} u

The value of the minimum is

\begin{array}{rcl} \sum u_{i}^{T} A_{i} u_{i} & = & \sum (\frac{1}{2} A_{i}^{- 1} E_{i}^{T} λ) A_{i} (\frac{1}{2} A_{i}^{- 1} E_{i}^{T} λ) \\ = & \frac{1}{4} λ^{T} (\sum E_{i} A_{i}^{- 1} E_{i}^{T}) λ \\ = & \frac{1}{4} λ^{T} C_{A S M}^{- 1} λ \\ = & u^{T} C_{A S M} C_{A S M}^{- 1} C_{A S M} u \\ = & u^{T} C_{A S M} u \end{array}

$◻$

77.4. The upper-bound by the overlap#

Typically, proving the estimate

‖ u ‖_{C_{A S M}}^{2} = inf_{\binom{u_{i} \in V_{i}}{u = \sum u_{i}}} \sum ‖ u_{i} ‖_{A}^{2} \leq \frac{1}{γ_{1}} ‖ u ‖_{A}^{2}

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 $O \in R^{m \times m}$ with entries

O_{i, j} := sup_{u_{i} \in V_{i}, v_{j} \in V_{j}} \frac{A (u_{i}, v_{j})}{‖ u_{i} ‖_{A} ‖ v_{j} ‖_{A}}

By the Cauchy-Schwarz inequality there is $0 \leq O_{i, j} \leq 1$ . The value $O_{i, j}$ leads to the so called strengthened Cauchy-Schwarz inequality

| A (u_{i}, v_{j}) | \leq O_{i, j} ‖ u_{i} ‖_{A} ‖ v_{j} ‖_{A}

If two sub-spaces are $A$ -orthogonal, then $O_{i, j} = 0$ .

Lemma There holds

$‖ u ‖_{A}^{2} \leq ρ (O) ‖ u ‖_{C_{A S M}}^{2},$

where $ρ (O)$ is the spectral radius of $O$ .

Proof: Let $u \in V_{h}$ be given, and let $u = \sum u_{i}$ be an arbitrary sub-space decomposition. Then

\begin{array}{rcl} ‖ u ‖_{A}^{2} & = & A (\sum_{i} u_{i}, \sum_{j} u_{i}) \\ = & \sum_{i, j} A (u_{i}, u_{j}) \\ \leq & \sum_{i, j} O_{i, j} ‖ u_{i} ‖_{A} ‖ u_{j} ‖_{A} \end{array}

Next, we define $z \in R^{N}$ as $z_{i} = ‖ u_{i} ‖_{A}$ . We use

z^{T} O z \leq ρ (O) ‖ z ‖_{2}^{2}

to bound

‖ u ‖_{A}^{2} \leq ρ (O) \sum_{i} ‖ u_{i} ‖_{A}^{2} .

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_{A S M}}^{2}$ .