Deflated and Multilevel Krylov Methods

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