An Adaptive Multigrid Method Based on Path Cover
An Adaptive Multigrid Method Based on Path Cover
复制标题
DOI：
10.1137/18m1194493
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Xiaozhe Hu;Junyuan Lin;L. Zikatanov
中科院分区：
文献类型：
--
作者：
Xiaozhe Hu;Junyuan Lin;L. Zikatanov
我们提出了一种路径覆盖自适应代数多重网格（PC-$\alpha$AMG）方法来求解加权图Laplacian线性方程组，并且也可以应用于离散的二阶椭圆型偏微分方程. PC-$\alpha$AMG基于非平滑聚合AMG（UA-AMG）。为了保持平滑误差的结构下降到粗水平，我们近似的水平集的平滑误差，首先形成顶点不相交的路径覆盖与以下的水平集的路径。然后通过沿路径覆盖中的路径进行沿着匹配来形成聚合。通过这种方式，我们能够以较低的计算成本构建多级结构。建议PC-$\alpha$AMG提供了一种机制，有效地重建多级层次结构的迭代过程中，导致一个快速的非线性多级算法。传统上，UA-AMG需要更复杂的循环技术，如AMLI-循环或K-循环，但正如我们的数值结果显示，PC-$\alpha$AMG提出这里导致几乎最优的标准V-循环算法求解线性系统的加权图拉普拉斯算子。对真实的图问题的数值实验也证明了PC-$\alpha$AMG的有效性和鲁棒性，特别是对病态图.
We propose a path cover adaptive algebraic multigrid (PC-$\alpha$AMG) method for solving linear systems of weighted graph Laplacians and 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 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 manner, we are able to build a multilevel structure at a low computational cost. The proposed PC-$\alpha$AMG provides a mechanism to efficiently re-build 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 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.