Multilevel Krylov Methods Reinhard Nabben Introduction
Deflated and Multilevel Krylov Methods Reinhard Nabben
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Outline
Multilevel Krylov Methods Reinhard Nabben
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
Multilevel Krylov methods
Numerical examples
Numerical examples
MK methods for Helmholtz equation
MK methods for Helmholtz equation
AMK methods Conclusion
AMK methods Conclusion
Multilevel Krylov Methods
How to solve Ax = b when • A is large (of dimension n > 106 )? • A is sparse? • A inherits properties from the underlying problem?
Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
Why to solve Ax = b?
MK methods for Helmholtz equation AMK methods
• many applications lead to Ax = b. • bottleneck of many complex algorithms.
Conclusion
Krylov subspace methods - CG method
Multilevel Krylov Methods Reinhard Nabben
A symmetric positive definite
Introduction Deflation, Projection methods
x0 start vector, r0 = b − Ax0 Kj (A, r0 ) = span{r0 , Ar0
, . . . , Aj−1 r
j-th step of CG method: find xj such that xj ∈ x0 + Kj (A, r0 )
0}
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
rj = b − Axj ⊥ Kj (A, r0 )
Krylov subspace methods - CG method CG method for Ax = b • Select arbitrary x0 • r0 := b − Ax0 p0 := r0 • FOR j := 0, 1, . . . , until convergence • αj := (rj , rj )/(pj , Apj ) • xj+1 := xj + αj pj • rj+1 := rj − αj Apj • βj := (rj+1 , rj+1 )/(rj , rj ) • pj+1 := rj+1 + βj pj • ENDFOR
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
√ j κ−1 ||x − xj ||A ≤ 2||x − x0 ||A √ , κ+1 λn κ = κ(A) = λ1
Classical Preconditioners
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods
Classical choices for M include • M −1 = αI, for α ≈ kAk (Richardson) • M −1 = αdiag(A) (Jacobi) •
M −1
•
M −1
= tril(A) (Gauss-Seidel) ˆU, ˆ for A = LU, L ˆ ≈ L, U ˆ ≈ U (ILU) =L
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods
Deflated CG
Reinhard Nabben Introduction
Nicolaides 1987, Mansfield 1988, 1990, Kolotilina 1998, Vuik, Segal, and Meijerink 1999, Morgan 1995, Saad, Yeung, Erhel, and Guyomarch 2000, Frank and Vuik 2001, Blaheta 2006
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
Deflation and restarted GMRES Morgan 1995, Erhel, Burrage, and Pohl 1996, Chapman and Saad 1997, Eiermann, Ernst, and Schneider 2000, Morgan 2002
Clemens et al. 2003,2004, de Sturler et al. 2006, Aksoylu, H. Klie, and M.F. Wheeler 2007
Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Deflation with eigenvectors
Multilevel Krylov Methods Reinhard Nabben Introduction
Aui = λi ui
Z = [u1 , . . . , ur ]
PD = I − AZ (Z T AZ )−1 Z T ,
uiT uj
= δij
Z ∈ Rn×r ,
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
spectrum(PD A) = {0, . . . , 0, λr +1 , . . . λn }
MK methods for Helmholtz equation AMK methods Conclusion
Deflation with general vectors
Multilevel Krylov Methods Reinhard Nabben
A symmetric positive definite
Introduction Deflation, Projection methods
Z = [z1 , . . . , zr ]
rankZ = r
E = Z T AZ
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
PD = I − AZE
−1
T
Z ,
Z ∈R
n×r
Numerical examples
,
MK methods for Helmholtz equation AMK methods
PD AZ = 0 spectrum(PD A) = {0, . . . , 0, µr +1 , . . . µn }
Conclusion
Deflated CG
Multilevel Krylov Methods Reinhard Nabben
Z ∈ Rn×r Ax = b We have:
Z = [z1 , . . . , zr ] rankZ = r PD = I − AZE −1 Z T
x = (I − PDT )x + PDT x
Compute both!
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
1. (I − PDT )x = Z (Z T AZ )−1 Z T b 2. Solve PD Ax˜ = PD b preconditioner M −1 : M −1 PD Ax˜ = M −1 PD b 3. Build PDT x˜ = PDT x
MK methods for Helmholtz equation AMK methods Conclusion
Deflation for linear systems
Multilevel Krylov Methods Reinhard Nabben
cg for singular system cg works if b ⊆ rangeA Speed of convergence condeff (PD A) = instead of cond(A) =
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid
λn (PD A) λr +1 (PD A) λn (A) λ1 (A)
Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
How to choose the z1 , . . . , zr ?
Multilevel Krylov Methods Reinhard Nabben Introduction
• best choice: eigenvectors • approximate eigenvectors, Ritz vectors • information from similar systems I I
several right hand sides within a non linear method
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Deflation M −1 preconditioner, ILU ZE −1 Z T
Multilevel Krylov Methods
Z appro. eigenvectors
Reinhard Nabben Introduction Deflation, Projection methods
Domain decomposition M −1 add. Schwarz Z grid transfer operator ZE −1 Z T coarse grid correction
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
Multigrid M −1 smoother Z grid transfer operator −1 T ZE Z coarse grid correction
MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods Reinhard Nabben
Name PREC AD DEF1 DEF2 A-DEF1 A-DEF2 BNN R-BNN1 R-BNN2
Method Traditional Preconditioned CG Additive Coarse Grid Correc. Deflation Variant 1 Deflation Variant 2 Adapted Deflation Variant 1 Adapted Deflation Variant 2 Abstract Balancing Reduced Balancing Variant 1 Reduced Balancing Variant 2 Q = ZE −1 Z T = Z (Z T AZ )−1 Z T
Operator M −1 M −1 + Q M −1 PD PDT M −1 M −1 PD + Q PDT M −1 + Q PDT M −1 PD + Q PDT M −1 PD PDT M −1
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods Reinhard Nabben
Name PREC AD DEF1 DEF2 A-DEF1 A-DEF2 BNN R-BNN1 R-BNN2
Method Traditional Preconditioned CG Additive Coarse Grid Correc. Deflation Variant 1 Deflation Variant 2 Adapted Deflation Variant 1 Adapted Deflation Variant 2 Abstract Balancing Reduced Balancing Variant 1 Reduced Balancing Variant 2
Operator M −1 M −1 + Q M −1 PD PDT M −1 M −1 PD + Q PDT M −1 + Q PDT M −1 PD + Q PDT M −1 PD PDT M −1
Q = ZE −1 Z T = Z (Z T AZ )−1 Z T Nabben, Vuik 04 , Nabben, Vuik 06, Nabben Vuik 08 Tang, Nabben, Vuik, Erlangga 07 Tang, MacLachlan, Nabben, Vuik 08
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods
Theorem Tang, Nabben, Vuik, Erlangga 07
The spectrum of the systems preconditioned by DEF1, DEF2, R-BNN1 or R-BNN2 is given by
{0, . . . , 0, µr +1 , . . . , µn }. The spectrum of the systems preconditioned by A-DEF1, A-DEF2, BNN is given by
Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation
{1, . . . , 1, µr +1 , . . . , µn }.
AMK methods Conclusion
Non-symmetric Problems
Multilevel Krylov Methods Reinhard Nabben
• Erlangga, Nabben 06:
Introduction
ZT
→
YT
E→
Deflation, Projection methods
Y T AZ
PD = I − AZE −1 Y T
Deflation, Domain Decomposition, Multigrid
PDT → QD = I − ZE −1 Y T A
Multilevel Krylov methods
PBNN =
QD M −1 PD
+
Numerical examples
ZE −1 Y T
MK methods for Helmholtz equation AMK methods
kM −1 (b
− Auk ,D )k2 ≤
kM −1 (b
− Auk ,BNN )k2 .
Conclusion
Multilevel Krylov methods (MK methods)
Multilevel Krylov Methods Reinhard Nabben
Erlangga, Nabben 07/08
Introduction Deflation, Projection methods
Au = b,
A ∈ CN×N ,
u, b ∈ CN .
A is in general nonsymmetric, sparse and large Problems: • Diffusion problem (symmetric) • Convection-diffusion equation (nonsymmetric) • Helmholtz equation (symmetric, indefinite) Preconditioned system: e M1−1 AM2−1 u
=
M1−1 b,
e = M2 u, u
M1 , M2 nonsingular.
Here, bu b b = b, A
b := M −1 A, A
b := u, u
b := M −1 b. b
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods
Consider
Reinhard Nabben
b −1 Y T , PN = PD + λN Z E
b = Y T AZ b , E
where b E b −1 Y T , PD = I − AZ
(Deflation)
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
and solve the system bu b b = PN b. PN A • Z , Y ∈ Rn×r are full rank
b Galerkin product • E: b • λN Approximation of largest eigenvalue of A.
Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
b Properties of PN A b b and PN A. Spectral relation between PD A
Multilevel Krylov Methods Reinhard Nabben Introduction
Theorem Z , Y are arbitrary rectangular matrices with rank r . b = {0, . . . , 0, µr +1 , . . . , µN } σ(PD A) b = {λN , . . . , λN , µr +1 , . . . , µN }. =⇒ σ(PN A)
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
b is similar to σ(PD A) b • σ(PN A)
MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov method
Multilevel Krylov Methods Reinhard Nabben Introduction
b −1 Y T , PN = PD + λN Z E
b = Y T AZ b , E
b H := E. b Need to solve the coarse system with A • PN is stable w.r.t. inexact solves. • Applying PN at the “second” level, i.e. use PN,H
b H xbH = bH instead of A b H xbH = PN,H bH solve: PN,H A using a Krylov method • With inner Krylov iterations, PN is i.g. not constant
Use flexible Krylov subspace method (FGMRES, FQMR, . . . )
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov method • The choice of Z and Y
Sparsity of Z and Y ; May be the same as prolongation and restriction matrices in multigrid (piece-wise constant, bi-linear interpolation, etc.); But not eigenvectors; Y = Z; • About λN
Expensive to compute, but an approximate is sufficient: → by Gerschgorin’s theorem.
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Numerical example: 2D Poisson equation
Multilevel Krylov Methods Reinhard Nabben
The 2D Poisson equation:
Introduction
−∇ · ∇u = g, u = 0,
2
in Ω ∈ (0, 1) , on Γ = ∂Ω.
Discretization: finite differences.
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
Ω with index set I = {i|ui ∈ Ω}. Ω is partitioned into non-overlapping subdomain Ωj , j = 1, . . . , l, with respective index Ij = {i ∈ I|ui ∈ Ωj }. Then, Z = [zij ]: ( 1, i ∈ Ij , zij = 0, i ∈ / Ij . Y =Z
Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Numerical example: 2D Poisson equation
Multilevel Krylov Methods Reinhard Nabben
Convergence results: relative residual ≤ 10−6 Gerschgorin estimate for λN N 322 642 1282 2562
MK(2,2,2) 15 16 16 16
MK(4,2,2) 14 14 14 14
MK(6,2,2) 14 14 14 14
MK(4,3,3) 14 14 14 14
• MK(4,2,2,): Multilevel Projection with 4,2,2
FGMRES iterations at level no. 2,3 and 4. etc. • MG: Multi Grid (here, V-cycle, one pre- and post
RB-GS smoothing, bilinear interpolation) Observation: • h-independent convergence • Convergence of MK is comparable with MG.
Introduction Deflation, Projection methods
MG 11 11 11 11
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
2D Convection-diffusion equation The 2D convection-diffusion equation with vertical winds:
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods
1 ∂u − ∇ · ∇u = 0, in Ω = (−1, 1)2 , ∂y Pe u(−1, y ) ≈ −1, u(1, y ) ≈ 1, u(x, −1) = x,
u(x, 1) = 0.
Discretization: Finite volume, upwind discretization for convective term Z : piece-wise constant interpolation, Y = Z b = M −1 A, M = diag(A) A
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
2D Convection-diffusion equation
Multilevel Krylov Methods Reinhard Nabben
Convergence results: relative residual ≤ 10−6 MK(4,2,2,2), Gerschgorin estimate for λN Pe: Grid 1282 2562 5122
20 16 16 15
50 16 16 16
100 18 16 16
200 24 17 15
• In MK, FGMRES is used • MG (with V-cycle, one pre- and post RB-GS
smoothing and bilinear interpolation) does not converge Observation: • Almost h- and Pe-independent convergence
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Conclusion - so far Comparison of deflation methods
Multilevel Krylov Methods Reinhard Nabben Introduction
Multilevel Krylov method (MK method) • preconditioner M • flexible Krylov method • multilevel structure (subspace systems) • restrictions, prolongations, deflation vectors etc. • estimates for λN .
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Conclusion - so far Comparison of deflation methods
Multilevel Krylov Methods Reinhard Nabben Introduction
Multilevel Krylov method (MK method) • preconditioner M • flexible Krylov method • multilevel structure (subspace systems) • restrictions, prolongations, deflation vectors etc. • estimates for λN . • h- and Pe-independent convergence
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Conclusion - so far Comparison of deflation methods
Multilevel Krylov Methods Reinhard Nabben Introduction
Multilevel Krylov method (MK method) • preconditioner M • flexible Krylov method • multilevel structure (subspace systems) • restrictions, prolongations, deflation vectors etc. • estimates for λN . • h- and Pe-independent convergence
Next: • Helmholtz equation • algebraic construction of restrictions, prolongations
algebraic MK methods, AMK methods
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Multilevel Krylov Methods
MK for Helmholtz equation: MKMG method
Reinhard Nabben Introduction
ω 2 ˆ u(x) = f (x) Au(x) := − ∇ · ∇ − (1 − iα) c
(1)
2
(x ∈ Ω = (0, L) ),
(Γ = ∂Ω).
√ ˆi = −1 0 ≤ α ≤ 0.1, attenuative (damping) factor ω = 2πf the angular frequency, with f the temporal frequency • c = c(x) the velocity data Applications: aero- and marineacoustics, electromagnetics, seismics, etc. • • •
Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
equipped with radiation condition: du ˆω −i u =0 dn c
Deflation, Projection methods
Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
MKMG method
Multilevel Krylov Methods Reinhard Nabben
Preconditioner for the Helmholtz equation: Erlangga, Vuik, Oosterlee, 2004: ω 2 M := −∇ · ∇ − (1 − βˆi) , c
β = (0, 1].
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
Discretization of M → M.
Numerical examples
M is inverted approximately by one multigrid iteration
MK methods for Helmholtz equation AMK methods Conclusion
MKMG method
Multilevel Krylov Methods Reinhard Nabben
Preconditioner for the Helmholtz equation: Erlangga, Vuik, Oosterlee, 2004: ω 2 M := −∇ · ∇ − (1 − βˆi) , c
β = (0, 1].
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods
Discretization of M → M.
Numerical examples
M is inverted approximately by one multigrid iteration
MK methods for Helmholtz equation AMK methods
b 2 := RA1 M −1 R T ≈ RA1 R T (RM1 R T )−1 RR T . A 1 R = ZT = Y
RT = P = Z
Conclusion
MKMG method
Multilevel Krylov Methods Reinhard Nabben
Multilevel Krylov-Multigrid (MKMG) Cycle
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
•: projection steps, ◦: multigrid cycle
Multilevel Krylov Methods
MKMG method
Reinhard Nabben
constant k := ωL/c. g/w means “#grid points per wavelength”.
g/w 15 20 30
20 11 12 11
40 14 13 12
MKMG(4,2,1) k: 60 80 100 120 15 17 20 22 15 16 18 21 12 13 13 15
200 39 30 24
300 64 45 39
g/w 15 20 30
20 11 12 11
40 14 13 12
60 14 15 12
Multilevel Krylov methods Numerical examples
AMK methods
100 18 15 13
120 21 16 14
200 27 20 15
• convergence almost independent of k (with
MK(8,2,1))
Deflation, Domain Decomposition, Multigrid
MK methods for Helmholtz equation
MKMG(8,2,1) k: 80 17 14 12
Introduction Deflation, Projection methods
300 39 28 19
Conclusion
AMK methods So far geometric restrictions, prolongations, coarse grids use AMG techniques in the MK method algebraic MK methods, AMK methods We used
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid
• Ruge-Stüben technique
Multilevel Krylov methods
• agglomeration-based technique
Numerical examples MK methods for Helmholtz equation
to build R and P, coarse grid matrix : RAP
AMK methods Conclusion
AMK for 2D Convection-diffusion equation 2D Convection-diffusion equation with rotating flow
Multilevel Krylov Methods Reinhard Nabben Introduction
∇ · ~c (x, y )u(x, y ) − ∆u(x, y ) = f (x, y ),
Ω ∈ (0, 1)2
homogeneous Dirichlet boundary conditions, ~c (x, y ) is the prescribed velocity vector field
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples
c1 (x, y ) = −Cxy (1 − x),
c2 (x, y ) = Cxy (1 − y ),
where C = 80.
MK methods for Helmholtz equation AMK methods Conclusion
Discretization: cell-centered finite volumes, uniform mesh
AMK for 2D Convection-diffusion equation
Multilevel Krylov Methods Reinhard Nabben
AMK(4,2,1)-AG AMK(4,2,1)-RS AMK(4,2,1)-AG-M AMK(4,2,1)-RS-M AMG-RS
# iterations for mesh: 162 322 642 1282 16 18 19 21 11 13 20 37 16 18 19 21 11 13 19 35 16 39 87 154
Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation
M = diag(Al )
AMK methods Conclusion
AMK for 2D Convection-diffusion equation Aggregation and Ruge-Stüben techniques
Multilevel Krylov Methods Reinhard Nabben Introduction Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
Conclusion Multilevel Krylov methods (MK methods)
Multilevel Krylov Methods Reinhard Nabben Introduction
Algebraic Multilevel Krylov methods (AMK methods)
• preconditioner M • flexible Krylov method • multilevel structure (subspace systems) • restrictions, prolongations, deflation vectors etc. • estimates for λN .
Deflation, Projection methods Deflation, Domain Decomposition, Multigrid Multilevel Krylov methods Numerical examples MK methods for Helmholtz equation AMK methods Conclusion
http://www.math.tu-berlin.de/˜nabben