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 34 articles , 1 standard article )

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

1 2 next

  1. Barker, Andrew T.; Gelever, Stephan V.; Lee, Chak S.; Osborn, Sarah V.; Vassilevski, Panayot S.: Multilevel spectral coarsening for graph Laplacian problems with application to reservoir simulation (2021)
  2. Chen, Chao; Liang, Tianyu; Biros, George: \textttrchol: randomized Cholesky factorization for solving SDD linear systems (2021)
  3. Cowen, Lenore; Devkota, Kapil; Hu, Xiaozhe; Murphy, James M.; Wu, Kaiyi: Diffusion state distances: multitemporal analysis, fast algorithms, and applications to biological networks (2021)
  4. Facca, Enrico; Benzi, Michele: Fast iterative solution of the optimal transport problem on graphs (2021)
  5. Gillani, Iqra Altaf; Bagchi, Amitabha: A queueing network-based distributed Laplacian solver (2021)
  6. Gottschalk, Hanno; Kahl, Karsten: Coarsening in algebraic multigrid using Gaussian processes (2021)
  7. Hu, Xiaozhe; Wu, Kaiyi; Zikatanov, Ludmil T.: A posteriori error estimates for multilevel methods for graph Laplacians (2021)
  8. Ye, Shuai; An, Hengbin; Xu, Xiaowen; Xu, Xinhai; Yang, Xuejun: A filter in constructing the preconditioner for solving linear equation systems of radiation diffusion problems (2021)
  9. Choi, Gary P. T.; Leung-Liu, Yusan; Gu, Xianfeng; Lui, Lok Ming: Parallelizable global conformal parameterization of simply-connected surfaces via partial welding (2020)
  10. Adrian, S. B.; Andriulli, F. P.; Eibert, T. F.: On a refinement-free Calderón multiplicative preconditioner for the electric field integral equation (2019)
  11. Benzi, Michele; Fika, Paraskevi; Mitrouli, Marilena: Graphs with absorption: numerical methods for the absorption inverse and the computation of centrality measures (2019)
  12. Franceschini, Andrea; Paludetto Magri, Victor A.; Mazzucco, Gianluca; Spiezia, Nicolò; Janna, Carlo: A robust adaptive algebraic multigrid linear solver for structural mechanics (2019)
  13. Hu, Xiaozhe; Lin, Junyuan; Zikatanov, Ludmil T.: An adaptive multigrid method based on path cover (2019)
  14. Hu, Xiaozhe; Vassilevski, Panayot S.: Modifying AMG coarse spaces with weak approximation property to exhibit approximation in energy Norm (2019)
  15. Paludetto Magri, Victor A.; Franceschini, Andrea; Janna, Carlo: A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems (2019)
  16. Fan, Zhou; Guan, Leying: Approximate (\ell_0)-penalized estimation of piecewise-constant signals on graphs (2018)
  17. 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)
  18. Kahl, Karsten; Rottmann, Matthias: Least angle regression coarsening in bootstrap algebraic multigrid (2018)
  19. Monnig, Nathan D.; Meyer, François G.: The resistance perturbation distance: a metric for the analysis of dynamic networks (2018)
  20. Shaydulin, Ruslan; Safro, Ilya: Aggregative coarsening for multilevel hypergraph partitioning (2018)

1 2 next