Multilevel Block Factorization Preconditioners

Matrix-based Analysis and Algorithms for Solving Finite Element Equations
1. Auflage 2008
ISBN: 978-0-387-71564-3
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 530 Seiten

Autoren/Hrsg.

Inhaltsverzeichnis

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