A short history of AGMG
(pdf version)
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, aggregationbased AMG, sometimes also referred to as UAAMG, 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 twolevel scheme is optimal when aggregates are formed in a sensible way;
 multilevel schemes are not optimal with the classical Vcycle,
but using the Kcycle make them converge nearly as fast as the twolevel variant.
These facts were first revealed in [2], where a model problem analysis of twolevel schemes is presented together with some numerical results for the Kcycle. The Kcycle (sometimes referred to as "non linear AMLI cycle") may be seen as a Wcycle with Krylov acceleration at all intermediate levels. It has been introduced and analyzed in [3].
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 aggregationbased AMG, and its competitiveness with respect to more classical AMG algorithms. Since then, an increasing number of papers exploits the fruitful idea of combining aggregationbased AMG with the Kcycle.
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.
 1

V. E. Bulgakov.
Multilevel iterative technique and aggregation concept with
semianalytical preconditioning for solving boundaryvalue problems.
Comm. Numer. Methods Engrg., 9:649657, 1993.
 2

A. C. Muresan and Y. Notay.
Analysis of aggregationbased multigrid.
SIAM J. Sci. Comput., 30:10821103, 2008.
[pdf ((c) SIAM)]
 3

Y. Notay and P. S. Vassilevski.
Recursive Krylovbased multigrid cycles.
Numer. Linear Algebra Appl., 15:473487, 2008.
 4

D. Braess.
Towards algebraic multigrid for elliptic problems of second order.
Computing, 55:379393, 1995.
 5

Y. Notay.
An aggregationbased algebraic multigrid method.
Electron. Trans. Numer. Anal., 37:123146, 2010.
[pdf]
 6

A. Napov and Y. Notay.
Algebraic analysis of aggregationbased multigrid.
Numer. Linear Algebra Appl., 18:539564, 2011.
 7

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

Y. Notay.
Aggregationbased algebraic multigrid for convectiondiffusion
equations.
SIAM J. Sci. Comput., 34:A2288A2316, 2012.
[pdf ((c) SIAM)]
 9

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

Y. Notay and A. Napov.
A massively parallel solver for discrete poissonlike problems.
Technical Report GANMN 1401, Université Libre de Bruxelles,
Brussels, Belgium, 2014.
[pdf].
Contact
Main AGMG page