TY - JOUR
T1 - A cascadic multigrid algorithm for computing the Fiedler vector of graph Laplacians
AU - Urschel, John C.
AU - Xu, Jinchao
AU - Hu, Xiaozhe
AU - Zikatanov, Ludmil T.
N1 - Generated from Scopus record by KAUST IRTS on 2023-02-15
PY - 2015/3/1
Y1 - 2015/3/1
N2 - In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.
AB - In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.
UR - http://global-sci.org/intro/article_detail/jcm/9837.html
UR - http://www.scopus.com/inward/record.url?scp=84929625101&partnerID=8YFLogxK
U2 - 10.4208/jcm.1412-m2014-0041
DO - 10.4208/jcm.1412-m2014-0041
M3 - Article
SN - 0254-9409
VL - 33
SP - 209
EP - 226
JO - Journal of Computational Mathematics
JF - Journal of Computational Mathematics
IS - 2
ER -