Multilevel block factorization preconditioners. Matrix-based analysis and algorithms for solving finite element equations.

*(English)*Zbl 1170.65001
New York, NY: Springer (ISBN 978-0-387-71563-6/hbk). xiv, 529 p. (2008).

This well-written and timely book fills a great need in the literature. It provides a thorough and yet readable treatment of contemporary theory and practice of block preconditioners, multigrid methods, and domain decomposition from a matrix perspective. The book includes a number of recent technical results, and some results and methods appear for the first time in a book form. Yet at least the first half of of the book will be readily accessible to graduate students past introductory analysis and linear algebra. There are many helpful and illustrative figures. From about the middle, the treatment grows progressively more advanced and terse and culminates in highly technical appendices. As the author states in the introduction, “some of the topics are only touched upon and offer a potential for further research.”

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 texbook on the topic.

Chapter 1 provides a lucid overview of prerequisites from finite elements, including basics of multigrid theory and mortar elements. The chapter also provides a theory of finite element agglomeration by boolean algebra. Chapter 2 then briefly describes the basics of iterative methods and preconditioning.

Chapter 3 and 4 provide a thorough treatment of two-block factorization in preconditioning, including Schur complements, strengthened Cauchy inequality, connections to two-level multigrid, approximate and incomplete block factorizations, band inverses, and frequency filtering decomposition.

Chapter 5 presents multigrid and multilevel methods and their theory from several points of view: classical, as block-factorization preconditioners, and as block Gauss-Seidel. This provides a natural transition to additive preconditioners, such as BPX [cf. J. H. Bramble, J. E. Pasciak, and J. Xu, Math. Comput. 55, No. 191, 1–22 (1990; Zbl 0703.65076)], and hierarchical bases.

Chapter 6 treats several algebraic multigrid (AMG) methods, from the classical AMG of the 1980s to recently developed element agglomeration and smoothed aggregation. The chapter is concluded by a new generalization and simplification of the multilevel theory for AMG by smooth aggregation [cf. P. Vaněk, M. Brezina and J. Mandel, Numer. Math. 88, No. 3, 559–579 (2001; Zbl 0992.65139)].

Domain decomposition methods are the topic of Chapter 7, again from a matrix perspective. The chapter includes domain imbedding methods, tensor product matrices, Schwarz methods, a new simplified analysis of the Bank-Holst paradigm [R. E. Bank and M. Holst, SIAM Rev. 45, No. 2, 291–323 (2003; Zbl 1028.65104)], classical analysis arguments for the FAC method, as well as brief sections on \(H\left({div}\right) \) and \(H\left( {curl}\right) \) preconditioning.

Chapter 8 gives a brief treatment a two-block preconditioner for nonsymmetric and indefinite problems, while Chapter 9 treats saddle point problems (including positive definite preconditioners and Uzawa method) at greater length.

Chapter 10 surveys variable-step iterative methods, where the preconditioner may change from step to step, such as when the preconditioner is another iterative method. Chapter 11 contains a brief treatment of inexact Newton methods for nonlinear problems, while Chapter 12 covers briefly some methods for constrained quadratic problems, which arize e.g. in obstacle problems and variational inequalities.

Seven appendices provide additional advanced technical material, including the generalized conjugate gradient method for nonsymmetric problems, details on hierarchical bases, mixed methods, finite elements for Maxwell’s equations, scales of Sobolev norms, and further multigrid theory.

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 texbook on the topic.

Chapter 1 provides a lucid overview of prerequisites from finite elements, including basics of multigrid theory and mortar elements. The chapter also provides a theory of finite element agglomeration by boolean algebra. Chapter 2 then briefly describes the basics of iterative methods and preconditioning.

Chapter 3 and 4 provide a thorough treatment of two-block factorization in preconditioning, including Schur complements, strengthened Cauchy inequality, connections to two-level multigrid, approximate and incomplete block factorizations, band inverses, and frequency filtering decomposition.

Chapter 5 presents multigrid and multilevel methods and their theory from several points of view: classical, as block-factorization preconditioners, and as block Gauss-Seidel. This provides a natural transition to additive preconditioners, such as BPX [cf. J. H. Bramble, J. E. Pasciak, and J. Xu, Math. Comput. 55, No. 191, 1–22 (1990; Zbl 0703.65076)], and hierarchical bases.

Chapter 6 treats several algebraic multigrid (AMG) methods, from the classical AMG of the 1980s to recently developed element agglomeration and smoothed aggregation. The chapter is concluded by a new generalization and simplification of the multilevel theory for AMG by smooth aggregation [cf. P. Vaněk, M. Brezina and J. Mandel, Numer. Math. 88, No. 3, 559–579 (2001; Zbl 0992.65139)].

Domain decomposition methods are the topic of Chapter 7, again from a matrix perspective. The chapter includes domain imbedding methods, tensor product matrices, Schwarz methods, a new simplified analysis of the Bank-Holst paradigm [R. E. Bank and M. Holst, SIAM Rev. 45, No. 2, 291–323 (2003; Zbl 1028.65104)], classical analysis arguments for the FAC method, as well as brief sections on \(H\left({div}\right) \) and \(H\left( {curl}\right) \) preconditioning.

Chapter 8 gives a brief treatment a two-block preconditioner for nonsymmetric and indefinite problems, while Chapter 9 treats saddle point problems (including positive definite preconditioners and Uzawa method) at greater length.

Chapter 10 surveys variable-step iterative methods, where the preconditioner may change from step to step, such as when the preconditioner is another iterative method. Chapter 11 contains a brief treatment of inexact Newton methods for nonlinear problems, while Chapter 12 covers briefly some methods for constrained quadratic problems, which arize e.g. in obstacle problems and variational inequalities.

Seven appendices provide additional advanced technical material, including the generalized conjugate gradient method for nonsymmetric problems, details on hierarchical bases, mixed methods, finite elements for Maxwell’s equations, scales of Sobolev norms, and further multigrid theory.

Reviewer: Jan Mandel (Denver)

##### MSC:

65-02 | Research exposition (monographs, survey articles) pertaining to numerical analysis |

65N55 | Multigrid methods; domain decomposition for boundary value problems involving PDEs |

65F10 | Iterative numerical methods for linear systems |

65F50 | Computational methods for sparse matrices |

15-02 | Research exposition (monographs, survey articles) pertaining to linear algebra |

35J25 | Boundary value problems for second-order elliptic equations |

35Q60 | PDEs in connection with optics and electromagnetic theory |

65H10 | Numerical computation of solutions to systems of equations |

65F35 | Numerical computation of matrix norms, conditioning, scaling |

65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |

65N30 | Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs |

65K10 | Numerical optimization and variational techniques |

49J40 | Variational inequalities |