Additive Schwarz method

Remarks

Each $P_i$ is self-adjoint and satisfies $0 \le a(P_i w, w) \le a(w, w)$, so $P$ is self-adjoint with eigenvalues at most $N + 1$. If $a(Pw, w) = 0$, then $P_i w = 0$ for all $i$, so $w$ is orthogonal to every $V_i$ and hence to $V$, and $w = 0$. For the identity, the choice $v_i = P_i P^{-1} v$ gives $\sum_i a(v_i, v_i) = a(v, P^{-1} v)$. For any other decomposition, $a(v, P^{-1} v) = \sum_i a(v_i, P_i P^{-1} v)$, and the Cauchy–Schwarz inequality gives $a(v, P^{-1} v) \le \sum_i a(v_i, v_i)$.

In matrix form, let $A$ be the symmetric positive definite stiffness matrix and let $R_i$ be the restriction to the unknowns of subdomain $i$. Then the method uses the preconditioner $M^{-1} = \sum_i R_i^T (R_i A R_i^T)^{-1} R_i$, and $M^{-1} A$ is the matrix of $P$. One applies it inside the conjugate gradient method, and the local solves can run in parallel. Take finite elements on overlapping subdomains of diameter $H$ with overlap $\delta$, and a coarse space $V_0$ on the coarse grid. Then the standard bound is $\kappa(P) \le C (1 + H/\delta)$, with $C$ independent of the mesh size and the number of subdomains. Without the coarse space, the bound degrades as the number of subdomains grows, because a single subdomain solve cannot carry information across the whole domain.

Going deeper

For a student

The identity for $a(P^{-1} v, v)$ is often called Lions' lemma, and it reduces the analysis to finding a stable splitting. It is the parallel counterpart of the Schwarz alternating method, just as the Jacobi method is the parallel counterpart of Gauss–Seidel. Coloring the subdomains so that overlapping ones get different colors improves the bound $N + 1$ to one plus the number of colors. The same abstract framework covers multigrid methods viewed as subspace corrections.