A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph\n Laplacians

2014/12/01 by John Urschel, Urschel, John C., Xiaozhe Hu +5 · 1 citation
Computer Science · Engineering · #65F15 #65N55 #68R10 #Advanced Numerical Methods in Computational Mathematics #Complexity and Algorithms in Graphs #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1412.0565

openalex publication_date 2014/12/01 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

In this paper, we develop a cascadic multigrid algorithm for fast computation\nof the Fiedler vector of a graph Laplacian, namely, the eigenvector\ncorresponding to the second smallest eigenvalue. This vector has been found to\nhave applications in fields such as graph partitioning and graph drawing. The\nalgorithm is a purely algebraic approach based on a heavy edge coarsening\nscheme and pointwise smoothing for refinement. To gain theoretical insight, we\nalso consider the related cascadic multigrid method in the geometric setting\nfor elliptic eigenvalue problems and show its uniform convergence under certain\nassumptions. Numerical tests are presented for computing the Fiedler vector of\nseveral practical graphs, and numerical results show the efficiency and\noptimality of our proposed cascadic multigrid algorithm.\n

Cited by

• Efficient Training of Deep Networks using Guided Spectral Data Selection: A Step Toward Learning What You Need

Related

• Improvement of the Cascadic Multigrid Algorithm with a Gauss Seidel\n Smoother to Efficiently Compute the Fiedler Vector of a Graph Laplacian
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
• Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver\n (Journal Version)
• Inverse Fiedler vector problem of a graph
• Auxiliary Space Multigrid Method Based on Additive Schur Complement Approximation for Graph Laplacian