Year: 2015
Author: John C. Urschel, Jinchao Xu, Xiaozhe Hu, Ludmil T. Zikatanov
Journal of Computational Mathematics, Vol. 33 (2015), Iss. 2 : pp. 209–226
Abstract
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.
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1412-m2014-0041
Journal of Computational Mathematics, Vol. 33 (2015), Iss. 2 : pp. 209–226
Published online: 2015-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 18
Keywords: Graph Laplacian Cascadic multigrid Fiedler vector Elliptic eigenvalue problems.
Author Details
-
Spectral Graph Partitioning Using Geodesic Distance-based Projection
Futamura, Yasunori | Wakaki, Ryota | Sakurai, Tetsuya2021 IEEE High Performance Extreme Computing Conference (HPEC), (2021), P.1
https://doi.org/10.1109/HPEC49654.2021.9622831 [Citations: 0] -
On the maximal error of spectral approximation of graph bisection
Urschel, John C. | Zikatanov, Ludmil T.Linear and Multilinear Algebra, Vol. 64 (2016), Iss. 10 P.1972
https://doi.org/10.1080/03081087.2015.1133557 [Citations: 5] -
Graphs with absorption: Numerical methods for the absorption inverse and the computation of centrality measures
Benzi, Michele | Fika, Paraskevi | Mitrouli, MarilenaLinear Algebra and its Applications, Vol. 574 (2019), Iss. P.123
https://doi.org/10.1016/j.laa.2019.03.026 [Citations: 4] -
On the convergence of an extrapolation cascadic multigrid method for elliptic problems
Hu, Hongling | Ren, Zhengyong | He, Dongdong | Pan, KejiaComputers & Mathematics with Applications, Vol. 74 (2017), Iss. 4 P.759
https://doi.org/10.1016/j.camwa.2017.05.023 [Citations: 20] -
Algebraic Multigrid for Least Squares Problems on Graphs with Applications to HodgeRank
Colley, Charles | Lin, Junyuan | Hu, Xiaozhe | Aeron, Shuchin2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), (2017), P.627
https://doi.org/10.1109/IPDPSW.2017.163 [Citations: 0] -
Fiedler Vector Approximation via Interacting Random Walks
Doshi, Vishwaraj | Eun, Do YoungProceedings of the ACM on Measurement and Analysis of Computing Systems, Vol. 4 (2020), Iss. 1 P.1
https://doi.org/10.1145/3379502 [Citations: 2] -
A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians
Hu, Xiaozhe | Wu, Kaiyi | Zikatanov, Ludmil T.SIAM Journal on Scientific Computing, Vol. 43 (2021), Iss. 5 P.S727
https://doi.org/10.1137/20M1349618 [Citations: 3] -
An Adaptive Multigrid Method Based on Path Cover
Hu, Xiaozhe | Lin, Junyuan | Zikatanov, Ludmil T.SIAM Journal on Scientific Computing, Vol. 41 (2019), Iss. 5 P.S220
https://doi.org/10.1137/18M1194493 [Citations: 10] -
The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning
Chen, Yannan | Qi, Liqun | Zhang, XiaoyanSIAM Journal on Scientific Computing, Vol. 39 (2017), Iss. 6 P.A2508
https://doi.org/10.1137/16M1094828 [Citations: 25] -
Performance-Portable Graph Coarsening for Efficient Multilevel Graph Analysis
Gilbert, Michael S. | Acer, Seher | Boman, Erik G. | Madduri, Kamesh | Rajamanickam, Sivasankaran2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), (2021), P.213
https://doi.org/10.1109/IPDPS49936.2021.00030 [Citations: 3] -
Maximizing Algebraic Connectivity of Constrained Graphs in Adversarial Environments
Anderson, Tor | Chang, Chin-Yao | Martinez, Sonia2018 European Control Conference (ECC), (2018), P.125
https://doi.org/10.23919/ECC.2018.8550531 [Citations: 3] -
Bringing physics into the coarse‐grid selection: Approximate diffusion distance/effective resistance measures for network analysis and algebraic multigrid for graph Laplacians and systems of elliptic partial differential equations
Lee, Barry
Numerical Linear Algebra with Applications, Vol. 31 (2024), Iss. 2
https://doi.org/10.1002/nla.2539 [Citations: 1] -
Finding diverse ways to improve algebraic connectivity through multi-start optimization
Mackay, Sarah | Ponce, Colin | Osborn, Sarah | McGarry, Meghan | Pinar, AliJournal of Complex Networks, Vol. 9 (2021), Iss. 1
https://doi.org/10.1093/comnet/cnab005 [Citations: 1] -
A Bootstrap Multigrid Eigensolver
Brannick, James | Cao, ShuhaoSIAM Journal on Matrix Analysis and Applications, Vol. 43 (2022), Iss. 4 P.1627
https://doi.org/10.1137/20M131151X [Citations: 1] -
Computing the diffusion state distance on graphs via algebraic multigrid and random projections
Lin, Junyuan | Cowen, Lenore J. | Hescott, Benjamin | Hu, XiaozheNumerical Linear Algebra with Applications, Vol. 25 (2018), Iss. 3
https://doi.org/10.1002/nla.2156 [Citations: 7] -
On the approximation of Laplacian eigenvalues in graph disaggregation
Hu, Xiaozhe | Urschel, John C. | Zikatanov, Ludmil T.Linear and Multilinear Algebra, Vol. 65 (2017), Iss. 9 P.1805
https://doi.org/10.1080/03081087.2016.1256944 [Citations: 1]