Matrix-based multigrid. Theory and applications

Publication date 17 November 2003

Published in Numerical Methods and Algorithms (Search for Journal in Brave)

algebraic multilevel method condition numbers conjugate gradient convergence domain decomposition finite differences finite elements finite volumes Helmholtz equation image processing incomplete LU mesh refinement multigrid multigrid algorithm relaxation methods semicoarsening textbook

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Stability and convergence of numerical methods for boundary value problems involving PDEs (65N12) Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs (65N50) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55)

Review text

The book consists of an introductory chapter, four parts, and an appendix. The introduction refers to some topics that the author sees as multilevel procedures, e.g., the representation of integer numbers with more than one digit or Euklid's algorithm for the determination of the greatest common divisor. [The reader may ask whether each recursive procedure is a multigrid algorithm.] Moreover, several topics as the wave transform are listed without details. Notations and an application of Gerschgorin's theorem to diagonally dominant matrices are added. Part I begins with a quick discussion of discretization methods for elliptic partial differential equations (finite differences, finite volumes, and finite elements). The iterative solution of linear equations (relaxation methods, conjugate gradient, and incomplete LU) is presented with emphasis on parallelization and cache-oriented codes. The general scheme of geometric and algebraic multigrid methods is described on seven pages. Part II on multigrid for structured grids with more than 50 pages is the greatest part in the book. Here the change from a presentation in terms of stencils to matrix-vector formulations is easily done in both directions. We find the automatic multigrid for the five-point stencil, a black-box multigrid method for the nine-point stencil, and the indefinite Helmholtz equation. Extra interest is given to semicoarsening and an application in image processing. Part III consists of one chapter. Grids with locally refined meshes are called semi-structured grids. A difference to the discussion in the previous part is that inner products are scaled now with respect to a diagonal matrix. Part IV on multigrid for unstructured grids refers to those grids that can be split into structured grids by domain decomposition. An alternative constitute the algebraic multilevel methods. Finally a C++ framework for unstructured grids is presented in an appendix. It is clear from the title that it is the intention of the book to focus on facts that can be stated in terms of matrices. Therefore, representations of the iteration matrices are provided, and some condition numbers are estimated. When the author speaks of the analysis of the multigrid method, he says how a convergence analysis could be done, but he does not perform it. Since convergence proofs refer to approximation properties directly or in an indirect way, they are beyond the scope of the book. Its intention is different.

Recommendations

Cited in

(7)

This page was built for publication: Matrix-based multigrid. Theory and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5907030)