Hardcover
Published: August 2008
ISBN: 9780387715636
Number Of Pages: 530
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.
Topics covered include the classical incomplete block-factorization preconditioners and the most efficient methods such as the multigrid, algebraic multigrid, and domain decomposition. Additionally, the author discusses preconditioning of saddle-point, nonsymmetric and indefinite problems, as well as preconditioning of certain nonlinear and quadratic constrained minimization problems that typically arise in contact mechanics. The book presents analytical as well as algorithmic aspects.
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.
From the reviews:
"This book by Panayot Vassilevski is the first comprehensive text in the literature on multilevel preconditioners in the formulation of approximate block factorizations. ... The presentation is comprehensive and detailed, and the theory is illustrated by classical examples of block factorizations like the block-ILU factorization. ... valuable addition to the collection of research books for any researcher working in the field of multilevel methods who is interested in getting a different view on methods he or she knows and has helped to develop and shape." (Martin J. Gander, Mathematical Reviews, Issue 2010 b)
"This well-written and timely book fills a great need in the literature. It provides a thorough and yet readable treatment of cotemporary theory ... . book will be readily accessible to graduate students past introductory analysis and linear algebra. ... The book will be a important reference for anyone interested in practical or theoretical aspects of iterative solvers for finite elements, from students to established researchers. Early chapters could serve well as a textbook on the topic." (Jan Mandel, Zentralblatt MATH, Vol. 1170, 2009)
"The presentation sets out with a tutorial on finite elements, where already properties of matrices which turn out essential later on are exhibited. ... this presentation will be of major interest to researchers and advanced students in that field." (H. Muthsam, Monatshefte fur Mathematik, Vol. 157 (1), May, 2009)
Preface | p. vii |
Motivation for Preconditioning | |
A Finite Element Tutorial | p. 3 |
Finite element matrices | p. 3 |
Finite element refinement | p. 9 |
Coarse-grid approximation | p. 10 |
The mass (Gram) matrix | p. 15 |
A "strong" approximation property | p. 18 |
The coarse-grid correction | p. 21 |
A f.e. (geometric) two-grid method | p. 22 |
Element matrices and matrix orderings | p. 25 |
Element topology | p. 29 |
Main definitions and constructions | p. 30 |
Element faces | p. 32 |
Faces of AEs | p. 34 |
Edges of AEs | p. 35 |
Vertices of AEs | p. 36 |
Nested dissection ordering | p. 36 |
Element agglomeration algorithms | p. 37 |
Finite element matrices on many processors | p. 39 |
The mortar method | p. 41 |
Algebraic construction of mortar spaces | p. 43 |
A Main Goal | p. 49 |
Block Factorization Preconditioners | |
Two-by-Two Block Matrices and Their Factorization | p. 55 |
Matrices of two-by-two block form | p. 55 |
Exact block-factorization. Schur complements | p. 55 |
Kato's Lemma | p. 60 |
Convergent iteration in A-norm | p. 61 |
Approximate block-factorization | p. 63 |
Product iteration matrix formula | p. 63 |
Block-factorizations and product iteration methods | p. 65 |
Definitions of two-level B[subscript TL] and two-grid B[subscript TG] preconditioners | p. 67 |
A main identity | p. 68 |
A simple lower-bound estimate | p. 70 |
Sharp upper bound | p. 70 |
The sharp spectral equivalence result | p. 72 |
Analysis of B[subscript TL] | p. 74 |
Analysis of B[subscript TG] | p. 75 |
Algebraic two-grid methods and preconditioners; sufficient conditions for spectral equivalence | p. 78 |
Classical two-level block-factorization preconditioners | p. 81 |
A general procedure of generating stable block-matrix partitioning | p. 84 |
Classical Examples of Block-Factorizations | p. 89 |
Block-ILU factorizations | p. 89 |
The M-matrix case | p. 92 |
Decay rates of inverses of band matrices | p. 98 |
Algorithms for approximate band inverses | p. 103 |
Wittum's frequency filtering decomposition | p. 109 |
Block-ILU factorizations with block-size reduction | p. 113 |
An alternative approximate block-LU factorization | p. 117 |
Odd-even modified block-ILU methods | p. 122 |
A nested dissection (approximate) inverse | p. 125 |
Multigrid (MG) | p. 129 |
From two-grid to multigrid | p. 129 |
MG as block Gauss-Seidel | p. 133 |
A MG analysis in general terms | p. 134 |
The XZ identity | p. 140 |
Some classical upper bounds | p. 144 |
Variable V-cycle | p. 152 |
MG with more recursive cycles; W-cycle | p. 157 |
Definition of a v-fold MG-cycle; complexity | p. 157 |
AMLI-cycle multigrid | p. 158 |
Analysis of AMLI | p. 159 |
Complexity of the AMLI-cycle | p. 162 |
Optimal W-cycle methods | p. 163 |
MG and additive MG | p. 165 |
The BPX-preconditioner | p. 165 |
Additive representation of MG | p. 166 |
Additive MG; convergence properties | p. 167 |
MG convergence based on results for matrix subblocks | p. 174 |
Cascadic multigrid | p. 177 |
Convergence in a stronger norm | p. 182 |
The hierarchical basis (HB) method | p. 185 |
The additive multilevel HB | p. 185 |
A stable multilevel hierarchical (direct) decomposition | p. 188 |
Approximation of L[subscript 2]-projections | p. 192 |
Construction of bases in the coordinate spaces | p. 195 |
The approximate wavelet hierarchical basis (or AWHB) | p. 196 |
Topics on Algebraic Multigrid (AMG) | p. 199 |
Motivation for the construction of P | p. 199 |
On the classical AMG construction of P | p. 202 |
On the constrained trace minimization construction of P | p. 205 |
On the coarse-grid selection | p. 207 |
On the sparsity pattern of P | p. 207 |
Coarsening by compatible relaxation | p. 208 |
Smoothing property and compatible relaxation | p. 209 |
Using inexact projections | p. 211 |
The need for adaptive AMG | p. 213 |
Smoothing based on "c"-"f" relaxation | p. 214 |
AMGe: An element agglomeration AMG | p. 225 |
Element-based construction of P | p. 226 |
On various norm bounds of P | p. 228 |
Multivector fitting interpolation | p. 234 |
Window-based spectral AMG | p. 235 |
Two-grid convergence of vector-preserving AMG | p. 241 |
The result of Vanek, Brezina, and Mandel | p. 249 |
Null vector-based polynomially smoothed bases | p. 249 |
Some properties of Chebyshev-like polynomials | p. 252 |
A general setting for the SA method | p. 255 |
Domain Decomposition (DD) Methods | p. 263 |
Nonoverlapping blocks | p. 263 |
Boundary extension mappings based on solving special coarse problems | p. 264 |
Weakly overlapping blocks | p. 267 |
Classical domain-embedding (DE) preconditioners | p. 270 |
DE preconditioners without extension mappings | p. 272 |
Fast solvers for tensor product matrices | p. 274 |
Schwarz methods | p. 280 |
Additive Schwarz preconditioners | p. 286 |
The domain decomposition paradigm of Bank and Holst | p. 291 |
Local error estimates | p. 300 |
The FAC method and related preconditioning | p. 304 |
Auxiliary space preconditioning methods | p. 313 |
Preconditioning Nonsymmetric and Indefinite Matrices | p. 319 |
An abstract setting | p. 319 |
A perturbation point of view | p. 323 |
Implementation | p. 325 |
Preconditioning Saddle-Point Matrices | p. 327 |
Basic properties of saddle-point matrices | p. 327 |
S.p.d. preconditioners | p. 330 |
Preconditioning based on "inf-sup" condition | p. 332 |
Transforming A to a positive definite matrix | p. 339 |
(Inexact) Uzawa and distributive relaxation methods | p. 341 |
Distributive relaxation | p. 341 |
The Bramble-Pasciak transformation | p. 342 |
A note on two-grid analysis | p. 344 |
Inexact Uzawa methods | p. 347 |
A constrained minimization approach | p. 353 |
Variable-Step Iterative Methods | p. 363 |
Variable-step (nonlinear) preconditioners | p. 363 |
Variable-step preconditioned CG method | p. 365 |
Variable-step multilevel preconditioners | p. 371 |
Variable-step AMLI-cycle MG | p. 372 |
Preconditioning Nonlinear Problems | p. 377 |
Problem formulation | p. 377 |
Choosing an accurate initial approximation | p. 379 |
The inexact Newton algorithm | p. 380 |
Quadratic Constrained Minimization Problems | p. 385 |
Problem formulation | p. 385 |
Projection methods | p. 386 |
A modified projection method | p. 389 |
Computable projections | p. 390 |
Dual problem approach | p. 391 |
Dual problem formulation | p. 391 |
Reduced problem formulation | p. 393 |
A monotone two-grid scheme | p. 397 |
Projected Gauss-Seidel | p. 398 |
Coarse-grid solution | p. 398 |
A monotone FAS constrained minimization algorithm | p. 401 |
Appendices | |
Generalized Conjugate Gradient Methods | p. 407 |
A general variational setting for solving nonsymmetric problems | p. 407 |
A quick CG guide | p. 410 |
The CG algorithm | p. 410 |
Preconditioning | p. 411 |
Best polynomial approximation property of CG | p. 412 |
A decay rate estimate for A[superscript -1] | p. 412 |
Properties of Finite Element Matrices. Further Details | p. 415 |
Piecewise linear finite elements | p. 415 |
A semilinear second-order elliptic PDE | p. 429 |
Stable two-level HB decomposition of finite element spaces | p. 433 |
A two-level hierarchical basis and related strengthened Cauchy-Schwarz inequality | p. 433 |
On the MG convergence uniform w.r.t. the mesh and jumps in the PDE coefficients | p. 438 |
Mixed methods for second-order elliptic PDEs | p. 439 |
Nonconforming elements and Stokes problem | p. 448 |
F.e. discretization of Maxwell's equations | p. 453 |
Computable Scales of Sobolev Norms | p. 457 |
H[superscript s]-stable decompositions | p. 457 |
Preliminary facts | p. 457 |
The main norm equivalence result | p. 459 |
The uniform coercivity property | p. 463 |
Multilevel Algorithms for Boundary Extension Mappings | p. 467 |
H[subscript 0 superscript 1]-norm Characterization | p. 471 |
Optimality of the L[subscript 2]-projections | p. 471 |
H[subscript 0 superscript 1]-stable decompositions of finite element functions | p. 475 |
MG Convergence Results for Finite Element Problems | p. 477 |
Requirements on the multilevel f.e. decompositions for the MG convergence analysis | p. 479 |
A MG for weighted H(curl) space | p. 487 |
A multilevel decomposition of weighted Nedelec spaces | p. 489 |
A multilevel decomposition of div-free Raviart-Thomas spaces | p. 495 |
A multilevel decomposition of weighted H(div)-space | p. 499 |
Some Auxiliary Inequalities | p. 507 |
Kantorovich's inequality | p. 507 |
An inequality between powers of matrices | p. 508 |
Energy bound of the nodal interpolation operator | p. 510 |
References | p. 513 |
Index | p. 527 |
Table of Contents provided by Ingram. All Rights Reserved. |
ISBN: 9780387715636
ISBN-10: 0387715630
Audience:
Professional
Format:
Hardcover
Language:
English
Number Of Pages: 530
Published: August 2008
Publisher: Springer-Verlag New York Inc.
Country of Publication: US
Dimensions (cm): 23.5 x 15.5
x 2.54
Weight (kg): 0.97