An Adaptive Multigrid Method Based on Path Cover
Xiaozhe Hu, Junyuan Lin, Ludmil Zikatanov · SIAM Journal on Scientific Computing · 2019
We propose a path cover adaptive algebraic multigrid (PC-$\alpha$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-$\alpha$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-$\alpha$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-$\alpha$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-$\alpha$AMG's effectiveness and robustness, especially for ill-conditioned graphs.