A short history of AGMG

The papers related to the AGMG project were certainly not the first to consider an algebraic multigrid method with coarsening based on (plain) aggregation (in short, aggregation-based AMG, sometimes also referred to as UA-AMG, for "unsmoothed aggregation AMG"). This approach traces back at least to works by Bulgakov [1]. However, to obtain a fast code, it was crucial to observe that

• the basic two-level scheme is optimal when aggregates are formed in a sensible way;
• multi-level schemes are not optimal with the classical V-cycle, but using the K-cycle make them converge nearly as fast as the two-level variant.

The aggregation procedure is also important. AGMG uses multiple passes of pairwise aggregation, following ideas that trace back to at least [4], with some improvements in the selection procedure based on the results in [2].

Altogether these ingredients form the method implemented in the first AGMG releases, and presented in [5]. In this paper, seemingly for the first time, extensive numerical results are reported that highlight the robustness and the efficiency of aggregation-based AMG, and its competitiveness with respect to more classical AMG algorithms. Since then, an increasing number of papers exploits the fruitful idea of combining aggregation-based AMG with the K-cycle.

The theoretical analysis, previously limited to some model configurations, has been generalized and improved in [6], leading in [7] to an enhanced aggregation algorithm, which is still based on multiple passes of pairwise matching (as in [4,5]), but uses a selection entirely based on a quality control: aggregates are formed in a way that is aware of their potential impact on the convergence rate. This principle was further extended in [8] to nonsymmetric problems. From version 3.0.0, the AGMG software uses this enhanced aggregation algorithm.

The latest developments include a study of AGMG for moderate order (P2, P3, P4) finite element matrices [9]; this latter work contains also a detailed comparison with the Boomer AMG module of hypre.

Finally, in [10] it is explained how the AGMG technology allows to obtain excellent weak scalability results on petascale computers, redesigning some critical components in a relatively simple yet not straightforward way.

References

1

V. E. Bulgakov.
Multi-level iterative technique and aggregation concept with semi-analytical preconditioning for solving boundary-value problems.
Comm. Numer. Methods Engrg., 9:649-657, 1993.

2

A. C. Muresan and Y. Notay.
Analysis of aggregation-based multigrid.
SIAM J. Sci. Comput., 30:1082-1103, 2008. [pdf ((c) SIAM)]

3

Y. Notay and P. S. Vassilevski.
Recursive Krylov-based multigrid cycles.
Numer. Linear Algebra Appl., 15:473-487, 2008.

4

D. Braess.
Towards algebraic multigrid for elliptic problems of second order.
Computing, 55:379-393, 1995.

5

Y. Notay.
An aggregation-based algebraic multigrid method.
Electron. Trans. Numer. Anal., 37:123-146, 2010. [pdf]

6

A. Napov and Y. Notay.
Algebraic analysis of aggregation-based multigrid.
Numer. Linear Algebra Appl., 18:539-564, 2011.

7

A. Napov and Y. Notay.
An algebraic multigrid method with guaranteed convergence rate.
SIAM J. Sci. Comput., 34:A1079-A1109, 2012. [pdf ((c) SIAM)]

8

Y. Notay.
Aggregation-based algebraic multigrid for convection-diffusion equations.
SIAM J. Sci. Comput., 34:A2288-A2316, 2012. [pdf ((c) SIAM)]

9

A. Napov and Y. Notay.
Algebraic multigrid for moderate order finite elements.
Technical Report GANMN 13-02, Université Libre de Bruxelles, Brussels, Belgium, 2013. [pdf].

10

Y. Notay and A. Napov.
A massively parallel solver for discrete poisson-like problems.
Technical Report GANMN 14-01, Université Libre de Bruxelles, Brussels, Belgium, 2014. [pdf].