full
search.png

Search

close.png

Cancel

arrow
Volume 33, Issue 2
A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

John C. Urschel, Jinchao Xu, Xiaozhe Hu & Ludmil T. Zikatanov

DOI: 10.4208/jcm.1412-m2014-0041

J. Comp. Math., 33 (2015), pp. 209-226.

Published online: 2015-04

[An open-access article; the PDF is free to any online user.]

Preview Full PDF 3709 34021

Cited by

google scholar semantic scholar
Export citation
  • 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.

  • Keywords

Graph Laplacian, Cascadic multigrid, Fiedler vector, Elliptic eigenvalue problems.

  • AMS Subject Headings

65N55, 65N25.

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

jcurschel@gmail.com (John C. Urschel)

xu@math.psu.edu (Jinchao Xu)

xiaozhe.hu@tufts.edu (Xiaozhe Hu)

ludmil@psu.edu (Ludmil T. Zikatanov)

  • BibTex
  • RIS
  • TXT
@Article{JCM-33-209, author = {Urschel , John C.Xu , JinchaoHu , Xiaozhe and Zikatanov , Ludmil T.}, title = {A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians}, journal = {Journal of Computational Mathematics}, year = {2015}, volume = {33}, number = {2}, pages = {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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1412-m2014-0041}, url = {http://global-sci.org/intro/article_detail/jcm/9837.html} }
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. JO - Journal of Computational Mathematics VL - 2 SP - 209 EP - 226 PY - 2015 DA - 2015/04 SN - 33 DO - http://doi.org/10.4208/jcm.1412-m2014-0041 UR - https://global-sci.org/intro/article_detail/jcm/9837.html KW - Graph Laplacian, Cascadic multigrid, Fiedler vector, Elliptic eigenvalue problems. 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.

Urschel , John C.Xu , JinchaoHu , Xiaozhe and Zikatanov , Ludmil T.. (2015). A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians. Journal of Computational Mathematics. 33 (2). 209-226. doi:10.4208/jcm.1412-m2014-0041
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard