Linear eq. Solvers (Ch6)

lin. system of eq (P69) (Ch6.0)

Preconditioning (Ch6.3)

iterative eq. solvers (Ch6.2)

direct lin. eq. solvers (Ch6.1)

Examples

Overlapping domain decomposition (ODD)

conjugate gradient method (P79)

Richardson iteration (aka simple- or Picard-iteration) (P73)

Basics

large dim & sparse matrices

Ana of multi-level preconditioner (Supp) = multi-level (P93)

Block-Jacobi (P84)
block-diagonal of $A$

Chebyshev (iteration) method (P77)

Additive Schwarz (P86)
overlapping block jacobi # generalization

block-elimination methods

gradient method (P77) #modification

Jacobi (P82)
$ C=\mathrm{diag} \, A $

general

2D-Dirichlet on square

...w/ coarse grid correction (P90)

1D-Dirichlet on interval

compute an $ A$-orthogonal (=conjugate) basis of the Krylov space $ \mathcal{K}_k(d_0) $

Algo

algorithm fulfills (Th77)

seq. $ p_k $ is $ A$-orth. and spans $ \mathcal{K}_k(d_0) $
$ u_k $ minimizes $ \min_{v \in u_0+\mathcal{K}_k(d_0)} \Vert u-v \Vert_A $
orth. $ d_k^T p_l = 0, \, \forall l< k $

convergence rate (Th78)

algo: $ u^{k+1}=u^k+\tau C^{-1}(f-Au^k) $

preconditioning action $ \sum_{i=1}^M E_i ( E_i^T A E_i )^{-1} E_i^T \underline{d} $

$ M $ can be bound in $ A $- and $ C $-norm (Le75)

Goal: construct $ C $ that

precond. action $ w=C^{-1} \times d $ efficiently computable
estimate spectral bounds

error in energy norm

quadratic form $ \underline{u}^T C \underline{u} = \sum_{i=1}^M \Vert GE_i \underline{u}_i \Vert^2_A$

rectangular embedding matrices $ E_i \in \mathbb{R}^{N \times N_i}, \, i=1,...,M $
$ \Rightarrow $ unique representation $ \underline{u}=\sum^M_{i=1} E_i \underline{u}_i $

local (P89)

terminates at finite number of steps (Re76)

Galerkin Isomorphism $ G:\mathbb{R}^N \rightarrow V_h : \underline{u} \rightarrow u = \sum u_i \varphi_i $
with dual $ G^*:V_h^* \rightarrow \mathbb{R}^N : d(\cdot ) \rightarrow (d( \varphi_i))_{i=1,...N} $

finite element spaces $ V_l $

$ h_l \simeq 2^{-l} $
$ N_l = \mathrm{dim}(V_l) $
$ \{ \varphi_{l,i}:1 \leq i \leq N_l \}$hat basis
$ A_l $ FE matrix

comparable to band factorization

goal:solve finite element system on $V_L=V_h \subset H^1 $

simple analysis (Le1)
$ \frac{1}{L}C \preceq A \preceq LC $

use finite element spaces $ V_0 \subset V_1 \subset ... \subset V_L $
on (hierarchy of) coarser meshes $ \mathcal{T}_0,\mathcal{T}_1,...,\mathcal{T}_L $

$ m $ iterations $ \Rightarrow $ overall convergence better w/ variable $ \tau_1,...,\tau_m $

eval. of quadratic form
$ \underline{u}^T A \underline{u} = A(G\underline{u},G\underline{u}) \simeq \Vert G \underline{u} \Vert^2_{H^1} $

Example on unit interval

Additive Schwarz Lemma = useful representation in quadr. form (Le80)
$ \underline{u}^T C \underline{u} = \inf_{\underline{u}_i \in \mathbb{R}^{N_i}}\sum_{i=1}^M \underline{u}_i^T A_i \underline{u}_i$
with $ A_i = E_i^T A E_i $

precond. action same as in Block-Jacobi

block factorization & sub structuring algos

LU-decomposition

optimization of $ \tau $ solved by chebyshev plynomials

preconditioning action $ \sum_{i=1}^N e_i ( e_i^T A e_i )^{-1}e_i^T \underline{d} $

result

FE space by sub-space splitting
$ V=\sum_{i=1}^M V_i, V_i=GE_i\mathbb{R}^{N_i}\subset V_h $

quadratic form $ \underline{u}^T C \underline{u} = \sum_{i=1}^N u_i^2 \Vert \varphi_i \Vert^2_A$

$ C=C_L$

Cholesky factorization

Add. Schwarz Lemma in finite element framework (= $ V_i, P_i, \widehat{u}$,...) (Le82)
$ \underline{u}^T C \underline{u} = \inf_{u_i \in V_i} \sum_{i=1}^M \Vert u_i \Vert_A^2 $

find automatically optimal $ \tau $ ,
by minimum in convex function per step

prolongation matrix $ E_H $
restriction matrix $ E_H^T $

original method not good choice

add one more sub spaces

$ \mathcal{T}_H $ coarse mesh
$ \mathcal{T}_h $ fine mesh by subdivision of $ \mathcal{T}_H $
$ V_H $ FE space on $ \mathcal{T}_H $
sub-space decomp. $ V_h=V_H + \sum _{i=1}^M V_i$

optimal number of subdomains $ M=N^{\frac{\alpha}{2\alpha -1}} $

asymptotic cost $ N^{\frac{\alpha^2}{2\alpha -1}} $+ Ex

problem: local ODD worse when number of sub-domains increase

preconditioning action $ \sum_{i=1} E_i ( E_i^T A E_i )^{-1} E_i^T \underline{d} + E_H ( E_H^T A E_H )^{-1} E_H^T \underline{d} $

improved estimate (Le2)
=fulfills optimal spectral bounds

iteration matrix $ M=I-\tau C^{-1}A $,
with $ u^{k+1}-u = M(u^k - u) $

Example on unit interval

optimal number of sub-domains

convergence rate estimated by Richardson iteration

preconditioner matrix $ C $

Decomposition of $ \Omega=\cup_{I=1}^M \Omega_i$ with

$ diam(\Omega_i)=H$
$ \Omega_i \subset \widetilde{\Omega}_i, \, \mathrm{dist}\{ \partial\widetilde{\Omega}_i \setminus \partial \Omega, \partial \Omega_i\} \succeq H $
only a small number of $ \widetilde{\Omega}_i $ overlap
FE mesh with $ h \leq H $
FE space by sub-space splitting
$ V_h=\sum V_i, V_i=V_h \cap H_0^1(\widetilde{\Omega}_i) $

can't be calculated $ \Rightarrow $ approx $ d^T_k C^{-1} d_k $

in the limit , if $ H \simeq h$ it is comparable to Jacobi-precond.

min-mesh size $ h $ of a shape-regular triang.(Th79)
$ \Rightarrow h^2 \underline{u}^T C \underline{u} \preceq u^T A u \preceq u^T C u $

graphical Ex (P91)

$ \Rightarrow $ (not necessarily) unique representation $ \underline{u}=\sum^M_{i=1} E_i \underline{u}_i $

better than general

band matrix -> faster

it fulfills optimal spectral estimates (Th84)
$ \underline{u}^T C \underline{u} \preceq \underline{u}^T A \underline{u} \preceq \underline{u}^T C \underline{u} $

(optimal) damping $ \tau $

3D worse

recursively

$ C_0^{-1}:= A_0^{-1}$
$ C_l^{-1}:=(\mathrm{diag}\,A_l)^{-1} + E_l C_{l-1}^{-1}E_l^T$

leading to optimal condition number $ \kappa(C^{-1}A)\preceq 1$ independent of $ L $

know a priori $ N_{its} $

goal: reduction by factor $ \epsilon $

ODD precond. fulfills spectral estimates (Le83)
$ H^2 \underline{u}^T C \underline{u} \preceq \underline{u}^T A \underline{u} \preceq \underline{u}^T C \underline{u} $

not numerically stable

intuitive explanation (P4)

2D very efficient

computation complexity of $ C_L^{-1}$ is $ O(N)$

$ C \preceq A \preceq C $