We present an algebraic multigrid method that has a guaranteed convergence rate for the class of nonsingular symmetric M-matrices with nonnegative row sum. A key ingredient is a new aggregation-based coarsening algorithm which insures that the two-grid convergence factor remains below a prescribed (user defined) parameter. This is achieved by using the bound in [2] based on the worst aggregates' ``quality''. For a sensible choice of this parameter, it is shown that the recursive use of the two-grid procedure yields a convergence independent of the number of levels, providing that one uses a proper AMLI-cycle. On the other hand, the computational cost per iteration step is of optimal order if the mean aggregates' size is large enough. This point is addressed analytically for the model Poisson problem and, further, numerically through a wide range of numerical experiments, demonstrating the robustness of the method. The experiments are performed on low order discretizations of second order elliptic PDEs in two and three dimensions, with both structured and unstructured grids, some of them with local refinement and/or reentering corner, and possible jumps or anisotropies in the PDE coefficients.
References
[1] A. Napov and Y. Notay, An algebraic multigrid method
with guaranteed convergence rate,
Report GANMN 10-03,
http://mntek3.ulb.ac.be/pub/docs/reports/pdf/ganmn1003.pdf
[2] A. Napov and Y. Notay, Algebraic analysis of aggregation-based multigrid, Numer. Lin. Alg. Appl., available in Wiley Online Library, DOI: 10.1002/nla.741