Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. 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.

References in zbMATH (referenced in 13 articles , 1 standard article )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Hou, Thomas Y.; Huang, De; Lam, Ka Chun; Zhang, PengChuan: An adaptive fast solver for a general class of positive definite matrices via energy decomposition (2018)
  2. Monnig, Nathan D.; Meyer, François G.: The resistance perturbation distance: a metric for the analysis of dynamic networks (2018)
  3. Adrian, S.B.; Andriulli, F.P.; Eibert, T.F.: A hierarchical preconditioner for the electric field integral equation on unstructured meshes based on primal and dual Haar bases (2017)
  4. Barker, Andrew T.; Lee, Chak S.; Vassilevski, Panayot S.: Spectral upscaling for graph Laplacian problems with application to reservoir simulation (2017)
  5. Chen, Yannan; Qi, Liqun; Zhang, Xiaoyan: The Fiedler vector of a Laplacian tensor for hypergraph partitioning (2017)
  6. Fox, Alyson; Manteuffel, Thomas; Sanders, Geoffrey: Numerical methods for Gremban’s expansion of signed graphs (2017)
  7. Napov, Artem; Notay, Yvan: An efficient multigrid method for graph Laplacian systems. II: Robust aggregation (2017)
  8. Xu, Jinchao; Zikatanov, Ludmil: Algebraic multigrid methods (2017)
  9. Napov, Artem; Notay, Yvan: An efficient multigrid method for graph Laplacian systems (2016)
  10. Notay, Yvan: Algebraic two-level convergence theory for singular systems (2016)
  11. Hateley, James C.; Wei, Huayi; Chen, Long: Fast methods for computing centroidal Voronoi tessellations (2015)
  12. Vassilevski, Panayot S.; Zikatanov, Ludmil T.: Commuting projections on graphs. (2014)
  13. Livne, Oren E.; Brandt, Achi: Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver (2012)