Algebraic multigrid with guaranteed convergence rate

28 October 2010

Algebraic multigrid methods are nowadays popular to solve linear systems arising from the discretization of elliptic PDEs. They try to combine the efficiency of well tuned specific schemes like classical (geometric-based) multigrid methods, with the ease of use of general purpose preconditioning techniques. This requires to define automatic coarsening procedures, which set up an hierarchy of coarse representations of the problem at hand using only information from the system matrix.

In this talk, we focus on aggregation-based algebraic multigrid methods. With these, the coarse unknowns are simply formed by grouping variables in disjoint subset called aggregates.

In the first part of the talk, we consider symmetric M-matrices with nonnegative row-sum. We show how aggregates can then be formed in such a way that the resulting method satisfies a prescribed bound on its convergence rate. That is, instead of the classical paradigm that applies an algorithm and then performs its analysis, the analysis is integrated in the set up phase so as to enforce minimal quality requirements. As a result, we obtain one of the first algebraic multigrid method with full convergence proof. The efficiency of the method is further illustrated by numerical results performed on finite difference or linear finite element discretizations of second order elliptic PDEs; the set of problems includes problems with jumps, anisotropy, reentering corners and/or unstructured meshes, sometimes with local refinement.

In the second part of the talk, we discuss nonsymmetric problems. We show how the previous approach can be extended to M-matrices with row- and column-sum both nonnegative, which includes some stable discretizations of convection-diffusion equations with divergence free convective flow. Some (preliminary) numerical results are also presented.

This is joint work with Artem Napov.

  • Computational Mathematics and Applications Seminar