Geodesic
An efficient multigrid method for graph Laplacian systems
Electronic transactions on numerical analysis, Tome 45 (2016), pp. 201-218.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 65F08, 65F10, 65N55, 65F50, 05C50
Keywords: graph Laplacian, multigrid, algebraic multigrid, multilevel, preconditioning, aggregation 
@article{ETNA_2016__45__a15,
     author = {Napov, Artem and Notay, Yvan},
     title = {An efficient multigrid method for graph {Laplacian} systems},
     journal = {Electronic transactions on numerical analysis},
     pages = {201--218},
     publisher = {mathdoc},
     volume = {45},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2016__45__a15/}
}
TY  - JOUR
AU  - Napov, Artem
AU  - Notay, Yvan
TI  - An efficient multigrid method for graph Laplacian systems
JO  - Electronic transactions on numerical analysis
PY  - 2016
SP  - 201
EP  - 218
VL  - 45
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ETNA_2016__45__a15/
LA  - en
ID  - ETNA_2016__45__a15
ER  - 
%0 Journal Article
%A Napov, Artem
%A Notay, Yvan
%T An efficient multigrid method for graph Laplacian systems
%J Electronic transactions on numerical analysis
%D 2016
%P 201-218
%V 45
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ETNA_2016__45__a15/
%G en
%F ETNA_2016__45__a15
Napov, Artem; Notay, Yvan. An efficient multigrid method for graph Laplacian systems. Electronic transactions on numerical analysis, Tome 45 (2016), pp. 201-218. http://geodesic.mathdoc.fr/item/ETNA_2016__45__a15/