Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
Authors:
- Oren E. LivneOLOren E. Livne
- Achi BrandtABAchi Brandt
Top Cited Papers
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 34 (4) , B499-B522
Abstract
Laplacian matrices of graphs arise in large-scale computational applications such as semisupervised machine learning; spectral clustering of images, genetic data, and web pages; transportation network flows; electrical resistor circuits; and elliptic partial differential equations discretized on unstructured grids with finite elements. A lean algebraic multigrid (LAMG) solver of the symmetric linear system $Ax=b$ is presented, where $A$ is a graph Laplacian. LAMG's run time and storage are empirically demonstrated to scale linearly with the number of edges. LAMG consists of a setup phase, during which a sequence of increasingly coarser Laplacian systems is constructed, and an iterative solve phase using multigrid cycles. General graphs pose algorithmic challenges not encountered in traditional multigrid applications. LAMG combines a lean piecewise-constant interpolation, judicious node aggregation based on a new node proximity measure (the affinity), and an energy correction of coarse-level systems. This results in fast convergence and substantial setup and memory savings. A serial LAMG implementation scaled linearly for a diverse set of 3774 real-world graphs with up to 47 million edges, with no parameter tuning. LAMG was more robust than the UMFPACK direct solver and combinatorial multigrid (CMG), although CMG was faster than LAMG on average. Our methodology is extensible to eigenproblems and other graph computations.
Keywords
All Related Versions
This publication has 44 references indexed in Scilit:
- A Bootstrap Algebraic Multilevel Method for Markov ChainsSIAM Journal on Scientific Computing, 2011
- Bootstrap AMGSIAM Journal on Scientific Computing, 2011
- Compatible Relaxation and Coarsening in Algebraic MultigridSIAM Journal on Scientific Computing, 2010
- Solving Elliptic Finite Element Systems in Near-Linear Time with Support PreconditionersSIAM Journal on Numerical Analysis, 2008
- Computation of Smallest Eigenvalues using Spectral Schur ComplementsSIAM Journal on Scientific Computing, 2005
- Maximum‐weight‐basis preconditionersNumerical Linear Algebra with Applications, 2004
- An Approximate Minimum Degree Ordering AlgorithmSIAM Journal on Matrix Analysis and Applications, 1996
- Variable steps for reversible integration methodsComputing, 1995
- Rigorous Quantitative Analysis of Multigrid, I. Constant Coefficients Two-Level Cycle with $L_2 $-NormSIAM Journal on Numerical Analysis, 1994
- Local Mesh Refinement Multilevel TechniquesSIAM Journal on Scientific and Statistical Computing, 1987