Paper Info
Title
An Adaptive Multigrid Method Based on Path Cover.
Abstract
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.
Year
DOI
Venue
2019
10.1137/18M1194493
SIAM JOURNAL ON SCIENTIFIC COMPUTING
Keywords
Field
DocType
unsmoothed aggregation algebraic multigrid method,adaptive method,graph Laplacian,path cover
Discretization,Mathematical optimization,Nonlinear system,Linear system,Level set,Algorithm,Robustness (computer science),Elliptic partial differential equation,Path cover,Multigrid method,Mathematics
Journal
Volume
Issue
ISSN
41
5
1064-8275
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Xiaozhe Hu14716.68
Junyuan Lin201.01
Ludmil Zikatanov318925.89