Multilevel Block Factorization Preconditioners (eBook)

Preface 6
Contents 8
Part I Motivation for Preconditioning 14
1 A Finite Element Tutorial 15
1.1 Finite element matrices 15
1.2 Finite element re.nement 21
1.3 Coarse-grid approximation 22
1.4 The mass (Gram) matrix 27
1.5 A strong” approximation property 30
1.6 The coarse-grid correction 33
1.7 A f.e. (geometric) two-grid method 34
1.8 Element matrices and matrix orderings 37
1.9 Element topology 41
1.10 Finite element matrices on many processors 51
1.11 The mortar method 53
2 A Main Goal 60
Part II Block Factorization Preconditioners 63
3 Two-by-Two Block Matrices and Their Factorization 64
3.1 Matrices of two-by-two block form 64
3.2 Approximate block-factorization 72
3.3 Algebraic two-grid methods and preconditioners sufficient conditions for spectral equivalence
3.4 Classical two-level block-factorization preconditioners 90
4 Classical Examples of Block-Factorizations 98
4.1 Block-ILU factorizations 98
4.2 The M-matrix case 101
4.3 Decay rates of inverses of band matrices 107
4.4 Algorithms for approximate band inverses 112
4.5 Wittum’s frequency filtering decomposition 118
4.6 Block-ILU factorizations with block-size reduction 122
4.7 An alternative approximate block-LU factorization 126
4.8 Odd–even modified block-ILU methods 131
4.9 A nested dissection (approximate) inverse 134
5 Multigrid (MG) 137
5.1 From two-grid to multigrid 137
5.2 MG as block Gauss–Seidel 141
5.3 A MG analysis in general terms 142
5.4 The XZ identity 148
5.5 Some classical upper bounds 152
5.6 MG with more recursive cycles W-cycle
5.7 MG and additive MG 173
5.8 Cascadic multigrid 185
5.9 The hierarchical basis (HB) method 193
Concluding comments for the chapter 205
6 Topics on Algebraic Multigrid (AMG) 206
6.1 Motivation for the construction of P 206
6.2 On the classical AMG construction of P 209
6.3 On the constrained trace minimization construction of P 212
6.4 On the coarse-grid selection 214
6.5 On the sparsity pattern of P 214
6.6 Coarsening by compatible relaxation 215
6.7 The need for adaptive AMG 220
6.8 Smoothing based on c”– f” relaxation 221
6.9 AMGe: An element agglomeration AMG 232
6.10 Multivector fitting interpolation 241
6.11 Window-based spectral AMG 242
6.12 Two-grid convergence of vector-preserving AMG 248
6.13 The result of Vanek, Brezina, and Mandel 256
7 Domain Decomposition (DD) Methods 269
7.1 Nonoverlapping blocks 269
7.2 Boundary extension mappings based on solving special coarse problems 270
7.3 Weakly overlapping blocks 273
7.4 Classical domain-embedding (DE) preconditioners 276
7.5 DE preconditioners without extension mappings 278
7.6 Fast solvers for tensor product matrices 280
7.7 Schwarz methods 286
7.8 Additive Schwarz preconditioners 292
7.9 The domain decomposition paradigm of Bank and Holst 297
7.10 The FAC method and related preconditioning 310
7.11 Auxiliary space preconditioning methods 319
8 Preconditioning Nonsymmetric and Indefinite Matrices 325
8.1 An abstract setting 325
8.2 A perturbation point of view 329
8.3 Implementation 331
9 Preconditioning Saddle-Point Matrices 332
9.1 Basic properties of saddle-point matrices 332
9.2 S.p.d. preconditioners 335
9.3 Transforming A to a positive definite matrix 344
9.4 (Inexact) Uzawa and distributive relaxation methods 346
9.5 A constrained minimization approach 358
10 Variable-Step Iterative Methods 367
10.1 Variable-step (nonlinear) preconditioners 367
10.2 Variable-step preconditioned CG method 369
10.3 Variable-step multilevel preconditioners 375
10.4 Variable-step AMLI-cycle MG 376
11 Preconditioning Nonlinear Problems 380
11.1 Problem formulation 380
11.2 Choosing an accurate initial approximation 382
11.3 The inexact Newton algorithm 383
12 Quadratic Constrained Minimization Problems 387
12.1 Problem formulation 387
12.2 Computable projections 392
12.3 Dual problem approach 393
12.4 A monotone two-grid scheme 399
12.5 A monotone FAS constrained minimization algorithm 403
Part III Appendices 406
A Generalized Conjugate Gradient Methods 407
A.1 A general variational setting for solving nonsymmetric problems 407
A.2 A quick CG guide 410
B Properties of Finite Element Matrices. Further Details 414
B.1 Piecewise linear .nite elements 414
B.2 A semilinear second-order elliptic PDE 428
B.3 Stable two-level HB decomposition of .nite element spaces 432
B.4 Mixed methods for second-order elliptic PDEs 438
B.5 Nonconforming elements and Stokes problem 447
B.6 F.e. discretization of Maxwell’s equations 452
C Computable Scales of Sobolev Norms 456
C.1 Hs-stable decompositions 456
C.2 Preliminary facts 456
C.3 The main norm equivalence result 458
C.4 The uniform coercivity property 462
D Multilevel Algorithms for Boundary Extension Mappings 465
E H1 0 -norm Characterization 469
E.1 Optimality of the L2-projections 469
F MG Convergence Results for Finite Element Problems 475
F.1 Requirements on the multilevel f.e. decompositions for the MG convergence analysis 477
F.2 A MG for weighted H(curl) space 485
F.3 A multilevel decomposition of div-free Raviart–Thomas spaces 493
F.4 A multilevel decomposition of weighted H(div)-space 497
G Some Auxiliary Inequalities 505
G.1 Kantorovich’s inequality 505
G.2 An inequality between powers of matrices 506
G.3 Energy bound of the nodal interpolation operator 508
References 511
Index 525