An efficient multigrid method for graph Laplacian systems II: robust aggregation

We consider the iterative solution of linear systems whose matrices are Laplacians of undirected graphs. Designing robust solvers for this class of problems is challenging due to the diversity of connectivity patterns encountered in practical applications. Our starting point is a recently proposed aggregation-based algebraic multigrid method that combines the recursive static elimination of the vertices of degree 1 with the degree-aware rooted aggregation (DRA) algorithm. The latter always produces aggregates big enough to ensure that the preconditioner cost per iteration is low. Here we further improve the robustness of the method by controlling the quality of the aggregates. More precisely, “bad” vertices are removed from the aggregates formed by the DRA algorithm until a quality test is passed. This ensures that the two-grid condition number is nicely bounded, whereas the cost per iteration is kept low by reforming too small aggregates when it happens that the mean aggregate size is not large enough. The effectiveness and the robustness of the resulting method are assessed on a large set of undirected graphs by comparing with the variant without quality control, as well as with another state-of-the art graph Laplacian solver.
SCOPUS: ar.j
info:eu-repo/semantics/published