An adaptive multigrid method based on path cover

We propose a path cover adaptive algebraic multigrid (PC-αAMG) method for solving linear systems with weighted graph Laplacians that can also be applied to discretized second order elliptic partial differential equations. The PC-αAMG is based on unsmoothed aggregation AMG (UA-AMG). To preserve the structure of smooth error down to the coarse levels, we approximate the level sets of the smooth error by first forming a vertex-disjoint path cover with paths following the level sets. The aggregations are then formed by matching along the paths in the path cover. In such a manner, we are able to build a multilevel structure at a low computational cost. The proposed PC-αAMG provides a mechanism to efficiently rebuild the multilevel hierarchy during the iterations and leads to a fast nonlinear multilevel algorithm. Traditionally, UA-AMG requires more sophisticated cycling techniques, such as AMLI-cycle or K-cycle, but as our numerical results show, the PC-αAMG proposed here leads to a nearly optimal standard V-cycle algorithm for solving linear systems with weighted graph Laplacians. Numerical experiments for some real-world graph problems also demonstrate PC-αAMG’s effectiveness and robustness, especially for ill-conditioned graphs.