Vassilevski 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
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 530 Seiten

This monograph is the first to provide a comprehensive, self-contained and rigorous presentation of some of the most powerful preconditioning methods for solving finite element equations in a common block-matrix factorization framework. The book covers both algorithms and analysis using a common block-matrix factorization approach which emphasizes its unique feature. Topics covered include the classical incomplete block-factorization preconditioners, the most efficient methods such as the multigrid, algebraic multigrid, and domain decomposition. This text can serve as an indispensable reference for researchers, graduate students, and practitioners. It can also be used as a supplementary text for a topics course in preconditioning and/or multigrid methods at the graduate level.

Autoren/Hrsg.

Vassilevski, Panayot S.

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