Volume 45, pp. 201-218, 2016.

An efficient multigrid method for graph Laplacian systems

Artem Napov and Yvan Notay

Abstract

We consider linear systems whose matrices are Laplacians of undirected graphs. We present a new aggregation-based algebraic multigrid method designed to achieve robustness for this class of problems, despite the diversity of connectivity patterns encountered in practical applications. These indeed range from regular mesh graphs to scale-free type of graphs associated with social networks. The method is based on the recursive static elimination of the vertices of degree 1 combined with a new Degree-aware Rooted Aggregation (DRA) algorithm. This algorithm always produces aggregates big enough so that the cost per iteration is low, whereas reasonable convergence is observed when the approach is combined with the K-cycle. The robustness of the resulting method is illustrated on a large collection of test problems, and its effectiveness is assessed via the comparison with a state-of-the-art reference method.

Full Text (PDF) [401 KB], BibTeX

Key words

graph Laplacian, multigrid, algebraic multigrid, multilevel, preconditioning, aggregation

AMS subject classifications

65F08, 65F10, 65N55, 65F50, 05C50

Links to the cited ETNA articles

[22]	Vol. 37 (2010), pp. 123-146 Yvan Notay: An aggregation-based algebraic multigrid method

ETNA articles which cite this article

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

< Back