An efficient method for graph Laplacian systems

We present a new aggregation-based algebraic multigrid method for the iterative solution of linear systems whose matrices are Laplacians of undirected graphs. It is challenging to achieve robustness for this class of problems because the connectivity patterns are very diverse. We propose and motivate an aggregation algorithm that 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