Solving Graph Laplacians via Multilevel Sparsifiers
From MaRDI portal
Publication:6405147
DOI10.1137/22M1503932arXiv2207.07847OpenAlexW4389725497MaRDI QIDQ6405147FDOQ6405147
Authors: X. Hu, Junyuan Lin 
Publication date: 16 July 2022
Abstract: We consider effective preconditioners for solving Laplacians of general weighted graphs. Theoretically, spectral sparsifiers (SSs) provide preconditioners of optimal computational complexity. However, they are not easy to use for real-world applications due to the implementation complications. Multigrid (MG) methods, on the contrary, are computationally efficient but lack of theoretical justifications. To bridge the gap between theory and practice, we adopt ideas of MG and SS methods and proposed preconditioners that can be used in practice with theoretical guarantees. We expand the original graph based on a multilevel structure to obtain an equivalent expanded graph. Although the expanded graph has a low diameter, a favorable property for constructing SSs, it has negatively weighted edges, which is an unfavorable property for the SSs. We design an algorithm to properly eliminate the negatively weighted edges and prove that the resulting expanded graph with positively weighted edges is spectrally equivalent to the expanded graph, thus, the original graph. Due to the low-diameter property of the positively-weighted expanded graph preconditioner (PEGP), existing algorithms for finding SSs can be easily applied. To demonstrate the advantage of working with the PEGP, we propose a type of SS, multilevel sparsifier preconditioner (MSP), that can be constructed in an easy and deterministic manner. We provide some preliminary numerical experiments to verify our theoretical findings and illustrate the practical effectiveness of PEGP and MSP in real-world applications.
Full work available at URL: https://doi.org/10.1137/22m1503932
Recommendations
- Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
- Algebraic multilevel preconditioners for the graph Laplacian based on matching in graphs
- Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
- Spectral sparsification of graphs
- Accelerated multigrid for graph Laplacian operators
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Iterative numerical methods for linear systems (65F10)
This page was built for publication: Solving Graph Laplacians via Multilevel Sparsifiers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405147)
