Please enable JavaScript.

Coggle requires JavaScript to display documents.

Linear eq. Solvers (Ch6) (Preconditioning (Ch6.3) (

Linear eq. Solvers (Ch6)

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

Examples

2D-Dirichlet on square

1D-Dirichlet on interval

large dim & sparse matrices

Preconditioning (Ch6.3)

Overlapping domain decomposition (ODD)

...w/ coarse grid correction (P90)

prolongation matrix \( E_H \)
restriction matrix \( E_H^T \)

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} \)

graphical Ex (P91)

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} \)

local (P89)

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) \)

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

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} \)

Basics

Goal: construct \( C \) that

precond. action \( w=C^{-1} \times d \) efficiently computable

estimate spectral bounds

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} \)

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} \)

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

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

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 \)

\( C=C_L\)

recursively

\( C_0^{-1}:= A_0^{-1}\)

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

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

improved estimate (Le2)
=fulfills optimal spectral bounds

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

intuitive explanation (P4)

\( C \preceq A \preceq C \)

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

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

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 \)

Example on unit interval

Additive Schwarz (P86)
overlapping block jacobi # generalization

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

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

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 \)

Example on unit interval

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

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

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

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

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 \)

iterative eq. solvers (Ch6.2)

conjugate gradient method (P79)

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)

error in energy norm

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

goal: reduction by factor \( \epsilon \)

terminates at finite number of steps (Re76)

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

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

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

preconditioner matrix \( C \)

(optimal) damping \( \tau \)

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

comparable to band factorization

Chebyshev (iteration) method (P77)

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

optimization of \( \tau \) solved by chebyshev plynomials

original method not good choice

know a priori \( N_{its} \)

not numerically stable

gradient method (P77) #modification

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

convergence rate estimated by Richardson iteration

direct lin. eq. solvers (Ch6.1)

block-elimination methods

block factorization & sub structuring algos

result

better than general

3D worse

2D very efficient

optimal number of sub-domains

general

LU-decomposition

Cholesky factorization

band matrix -> faster