Volume 37, pp. 123-146, 2010.

An aggregation-based algebraic multigrid method

Yvan Notay

Abstract

An algebraic multigrid method is presented to solve large systems of linear equations. The coarsening is obtained by aggregation of the unknowns. The aggregation scheme uses two passes of a pairwise matching algorithm applied to the matrix graph, resulting in most cases in a decrease of the number of variables by a factor slightly less than four. The matching algorithm favors the strongest negative coupling(s), inducing a problem dependent coarsening. This aggregation is combined with piecewise constant (unsmoothed) prolongation, ensuring low setup cost and memory requirements. Compared with previous aggregation-based multigrid methods, the scalability is enhanced by using a so-called K-cycle multigrid scheme, providing Krylov subspace acceleration at each level. This paper is the logical continuation of [SIAM J. Sci. Comput., 30 (2008), pp. 1082–1103], where the analysis of a anisotropic model problem shows that aggregation-based two-grid methods may have optimal order convergence, and of [Numer. Lin. Alg. Appl., 15 (2008), pp. 473–487], where it is shown that K-cycle multigrid may provide optimal or near optimal convergence under mild assumptions on the two-grid scheme. Whereas in these papers only model problems with geometric aggregation were considered, here a truly algebraic method is presented and tested on a wide range of discrete second order scalar elliptic PDEs, including nonsymmetric and unstructured problems. Numerical results indicate that the proposed method may be significantly more robust as black box solver than the classical AMG method as implemented in the code AMG1R5 by K. Stüben. The parallel implementation of the method is also discussed. Satisfactory speedups are obtained on a medium size multi-processor cluster that is typical of today computer market. A code implementing the method is freely available for download both as a FORTRAN program and a MATLAB function.

Full Text (PDF) [684 KB], BibTeX

Key words

Multigrid, linear systems, iterative methods, AMG, preconditioning, parallel computing.

AMS subject classifications

65F10, 65N55.

ETNA articles which cite this article

Vol. 37 (2010), pp. 351-366 Maximilian Emans: Benchmarking aggregation AMG for linear systems in CFD simulations of compressible internal flows

Vol. 45 (2016), pp. 201-218 Artem Napov and Yvan Notay: An efficient multigrid method for graph Laplacian systems

Vol. 51 (2019), pp. 118-134 Artem Napov and Ronan Perrussel: Revisiting aggregation-based multigrid for edge elements

Vol. 54 (2021), pp. 514-533 Hanno Gottschalk and Karsten Kahl: Coarsening in algebraic multigrid using Gaussian processes

Vol. 55 (2022), pp. 687-705 Abdeselam El Haman Abdeselam, Artem Napov, and Yvan Notay: Porting an aggregation-based algebraic multigrid method to GPUs

Vol. 58 (2023), pp. 629-656 Siobhán Correnty, Elias Jarlebring, and Daniel B. Szyld: Preconditioned Chebyshev BiCG method for parameterized linear systems

Vol. 60 (2024), pp. 169-196 Loïc Gouarin and Nicole Spillane: Fully algebraic domain decomposition preconditioners with adaptive spectral bounds

< Back