Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver

DOI10.1137/110843563zbMath1253.65045arXiv1108.0123OpenAlexW2070448527MaRDI QIDQ3165438

Publication date: 26 October 2012

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.0123

zbMATH Keywords

convergence numerical examples graph Laplacian eigenproblems symmetric linear system graph computation lean algebraic multigrid solver linear-scaling numerical linear solver piecewise-constant interpolation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Iterative numerical methods for linear systems (65F10)

Related Items (42)

A Unified Framework for Structured Graph Learning via Spectral Constraints ⋮ Unnamed Item ⋮ Least Angle Regression Coarsening in Bootstrap Algebraic Multigrid ⋮ Unnamed Item ⋮ Persistent Laplacians: Properties, Algorithms and Implications ⋮ Asymptotic spectra of large (grid) graphs with a uniform local structure. II: Numerical applications ⋮ Graphs with absorption: numerical methods for the absorption inverse and the computation of centrality measures ⋮ Iterative solution of spatial network models by subspace decomposition ⋮ The Fiedler Vector of a Laplacian Tensor for Hypergraph Partitioning ⋮ Algebraic multigrid methods ⋮ A hierarchical preconditioner for the electric field integral equation on unstructured meshes based on primal and dual Haar bases ⋮ MGIC: Multigrid-in-Channels Neural Network Architectures ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Spectral Upscaling for Graph Laplacian Problems with Application to Reservoir Simulation ⋮ An Efficient Multigrid Method for Graph Laplacian Systems II: Robust Aggregation ⋮ Numerical Methods for Gremban's Expansion of Signed Graphs ⋮ Parallelizable Global Conformal Parameterization of Simply-Connected Surfaces via Partial Welding ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A queueing network-based distributed Laplacian solver ⋮ Accelerated multigrid for graph Laplacian operators ⋮ An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition ⋮ A robust adaptive algebraic multigrid linear solver for structural mechanics ⋮ A filter in constructing the preconditioner for solving linear equation systems of radiation diffusion problems ⋮ A Novel Algebraic Multigrid Approach Based on Adaptive Smoothing and Prolongation for Ill-Conditioned Systems ⋮ Chronos: A General Purpose Classical AMG Solver for High Performance Computing ⋮ Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs ⋮ A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians ⋮ Unnamed Item ⋮ Coarsening in algebraic multigrid using Gaussian processes ⋮ LAMG ⋮ On a refinement-free Calderón multiplicative preconditioner for the electric field integral equation ⋮ Algebraic Two-Level Convergence Theory for Singular Systems ⋮ Modifying AMG Coarse Spaces with Weak Approximation Property to Exhibit Approximation in Energy Norm ⋮ Unnamed Item ⋮ An Adaptive Multigrid Method Based on Path Cover ⋮ Fast Iterative Solution of the Optimal Transport Problem on Graphs ⋮ Diffusion State Distances: Multitemporal Analysis, Fast Algorithms, and Applications to Biological Networks ⋮ Commuting projections on graphs ⋮ Multilevel Spectral Coarsening for Graph Laplacian Problems with Application to Reservoir Simulation ⋮ RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems ⋮ Fast methods for computing centroidal Voronoi tessellations

Uses Software

This page was built for publication: Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver