+612 9045 4394
Multilevel Block Factorization Preconditioners : Matrix-Based Analysis and Algorithms for Solving Finite Element Equations :  Matrix-Based Analysis and Algorithms for Solving Finite Element Equations - Panayot S. Vassilevski

Multilevel Block Factorization Preconditioners : Matrix-Based Analysis and Algorithms for Solving Finite Element Equations

Matrix-Based Analysis and Algorithms for Solving Finite Element Equations

Hardcover Published: August 2008
ISBN: 9780387715636
Number Of Pages: 530

Share This Book:


or 4 easy payments of $50.99 with Learn more
Ships in 5 to 9 business days

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.

Industry Reviews

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)

Prefacep. vii
Motivation for Preconditioning
A Finite Element Tutorialp. 3
Finite element matricesp. 3
Finite element refinementp. 9
Coarse-grid approximationp. 10
The mass (Gram) matrixp. 15
A "strong" approximation propertyp. 18
The coarse-grid correctionp. 21
A f.e. (geometric) two-grid methodp. 22
Element matrices and matrix orderingsp. 25
Element topologyp. 29
Main definitions and constructionsp. 30
Element facesp. 32
Faces of AEsp. 34
Edges of AEsp. 35
Vertices of AEsp. 36
Nested dissection orderingp. 36
Element agglomeration algorithmsp. 37
Finite element matrices on many processorsp. 39
The mortar methodp. 41
Algebraic construction of mortar spacesp. 43
A Main Goalp. 49
Block Factorization Preconditioners
Two-by-Two Block Matrices and Their Factorizationp. 55
Matrices of two-by-two block formp. 55
Exact block-factorization. Schur complementsp. 55
Kato's Lemmap. 60
Convergent iteration in A-normp. 61
Approximate block-factorizationp. 63
Product iteration matrix formulap. 63
Block-factorizations and product iteration methodsp. 65
Definitions of two-level B[subscript TL] and two-grid B[subscript TG] preconditionersp. 67
A main identityp. 68
A simple lower-bound estimatep. 70
Sharp upper boundp. 70
The sharp spectral equivalence resultp. 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 equivalencep. 78
Classical two-level block-factorization preconditionersp. 81
A general procedure of generating stable block-matrix partitioningp. 84
Classical Examples of Block-Factorizationsp. 89
Block-ILU factorizationsp. 89
The M-matrix casep. 92
Decay rates of inverses of band matricesp. 98
Algorithms for approximate band inversesp. 103
Wittum's frequency filtering decompositionp. 109
Block-ILU factorizations with block-size reductionp. 113
An alternative approximate block-LU factorizationp. 117
Odd-even modified block-ILU methodsp. 122
A nested dissection (approximate) inversep. 125
Multigrid (MG)p. 129
From two-grid to multigridp. 129
MG as block Gauss-Seidelp. 133
A MG analysis in general termsp. 134
The XZ identityp. 140
Some classical upper boundsp. 144
Variable V-cyclep. 152
MG with more recursive cycles; W-cyclep. 157
Definition of a v-fold MG-cycle; complexityp. 157
AMLI-cycle multigridp. 158
Analysis of AMLIp. 159
Complexity of the AMLI-cyclep. 162
Optimal W-cycle methodsp. 163
MG and additive MGp. 165
The BPX-preconditionerp. 165
Additive representation of MGp. 166
Additive MG; convergence propertiesp. 167
MG convergence based on results for matrix subblocksp. 174
Cascadic multigridp. 177
Convergence in a stronger normp. 182
The hierarchical basis (HB) methodp. 185
The additive multilevel HBp. 185
A stable multilevel hierarchical (direct) decompositionp. 188
Approximation of L[subscript 2]-projectionsp. 192
Construction of bases in the coordinate spacesp. 195
The approximate wavelet hierarchical basis (or AWHB)p. 196
Topics on Algebraic Multigrid (AMG)p. 199
Motivation for the construction of Pp. 199
On the classical AMG construction of Pp. 202
On the constrained trace minimization construction of Pp. 205
On the coarse-grid selectionp. 207
On the sparsity pattern of Pp. 207
Coarsening by compatible relaxationp. 208
Smoothing property and compatible relaxationp. 209
Using inexact projectionsp. 211
The need for adaptive AMGp. 213
Smoothing based on "c"-"f" relaxationp. 214
AMGe: An element agglomeration AMGp. 225
Element-based construction of Pp. 226
On various norm bounds of Pp. 228
Multivector fitting interpolationp. 234
Window-based spectral AMGp. 235
Two-grid convergence of vector-preserving AMGp. 241
The result of Vanek, Brezina, and Mandelp. 249
Null vector-based polynomially smoothed basesp. 249
Some properties of Chebyshev-like polynomialsp. 252
A general setting for the SA methodp. 255
Domain Decomposition (DD) Methodsp. 263
Nonoverlapping blocksp. 263
Boundary extension mappings based on solving special coarse problemsp. 264
Weakly overlapping blocksp. 267
Classical domain-embedding (DE) preconditionersp. 270
DE preconditioners without extension mappingsp. 272
Fast solvers for tensor product matricesp. 274
Schwarz methodsp. 280
Additive Schwarz preconditionersp. 286
The domain decomposition paradigm of Bank and Holstp. 291
Local error estimatesp. 300
The FAC method and related preconditioningp. 304
Auxiliary space preconditioning methodsp. 313
Preconditioning Nonsymmetric and Indefinite Matricesp. 319
An abstract settingp. 319
A perturbation point of viewp. 323
Implementationp. 325
Preconditioning Saddle-Point Matricesp. 327
Basic properties of saddle-point matricesp. 327
S.p.d. preconditionersp. 330
Preconditioning based on "inf-sup" conditionp. 332
Transforming A to a positive definite matrixp. 339
(Inexact) Uzawa and distributive relaxation methodsp. 341
Distributive relaxationp. 341
The Bramble-Pasciak transformationp. 342
A note on two-grid analysisp. 344
Inexact Uzawa methodsp. 347
A constrained minimization approachp. 353
Variable-Step Iterative Methodsp. 363
Variable-step (nonlinear) preconditionersp. 363
Variable-step preconditioned CG methodp. 365
Variable-step multilevel preconditionersp. 371
Variable-step AMLI-cycle MGp. 372
Preconditioning Nonlinear Problemsp. 377
Problem formulationp. 377
Choosing an accurate initial approximationp. 379
The inexact Newton algorithmp. 380
Quadratic Constrained Minimization Problemsp. 385
Problem formulationp. 385
Projection methodsp. 386
A modified projection methodp. 389
Computable projectionsp. 390
Dual problem approachp. 391
Dual problem formulationp. 391
Reduced problem formulationp. 393
A monotone two-grid schemep. 397
Projected Gauss-Seidelp. 398
Coarse-grid solutionp. 398
A monotone FAS constrained minimization algorithmp. 401
Generalized Conjugate Gradient Methodsp. 407
A general variational setting for solving nonsymmetric problemsp. 407
A quick CG guidep. 410
The CG algorithmp. 410
Preconditioningp. 411
Best polynomial approximation property of CGp. 412
A decay rate estimate for A[superscript -1]p. 412
Properties of Finite Element Matrices. Further Detailsp. 415
Piecewise linear finite elementsp. 415
A semilinear second-order elliptic PDEp. 429
Stable two-level HB decomposition of finite element spacesp. 433
A two-level hierarchical basis and related strengthened Cauchy-Schwarz inequalityp. 433
On the MG convergence uniform w.r.t. the mesh and jumps in the PDE coefficientsp. 438
Mixed methods for second-order elliptic PDEsp. 439
Nonconforming elements and Stokes problemp. 448
F.e. discretization of Maxwell's equationsp. 453
Computable Scales of Sobolev Normsp. 457
H[superscript s]-stable decompositionsp. 457
Preliminary factsp. 457
The main norm equivalence resultp. 459
The uniform coercivity propertyp. 463
Multilevel Algorithms for Boundary Extension Mappingsp. 467
H[subscript 0 superscript 1]-norm Characterizationp. 471
Optimality of the L[subscript 2]-projectionsp. 471
H[subscript 0 superscript 1]-stable decompositions of finite element functionsp. 475
MG Convergence Results for Finite Element Problemsp. 477
Requirements on the multilevel f.e. decompositions for the MG convergence analysisp. 479
A MG for weighted H(curl) spacep. 487
A multilevel decomposition of weighted Nedelec spacesp. 489
A multilevel decomposition of div-free Raviart-Thomas spacesp. 495
A multilevel decomposition of weighted H(div)-spacep. 499
Some Auxiliary Inequalitiesp. 507
Kantorovich's inequalityp. 507
An inequality between powers of matricesp. 508
Energy bound of the nodal interpolation operatorp. 510
Referencesp. 513
Indexp. 527
Table of Contents provided by Ingram. All Rights Reserved.

ISBN: 9780387715636
ISBN-10: 0387715630
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 530
Published: August 2008
Publisher: Springer-Verlag New York Inc.
Country of Publication: US
Dimensions (cm): 24.13 x 15.88  x 2.54
Weight (kg): 0.86