LAMG
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.
Keywords for this software
References in zbMATH (referenced in 26 articles , 1 standard article )
Showing results 1 to 20 of 26.
Sorted by year (- Choi, Gary P. T.; Leung-Liu, Yusan; Gu, Xianfeng; Lui, Lok Ming: Parallelizable global conformal parameterization of simply-connected surfaces via partial welding (2020)
- Adrian, S. B.; Andriulli, F. P.; Eibert, T. F.: On a refinement-free Calderón multiplicative preconditioner for the electric field integral equation (2019)
- Benzi, Michele; Fika, Paraskevi; Mitrouli, Marilena: Graphs with absorption: numerical methods for the absorption inverse and the computation of centrality measures (2019)
- Franceschini, Andrea; Paludetto Magri, Victor A.; Mazzucco, Gianluca; Spiezia, Nicolò; Janna, Carlo: A robust adaptive algebraic multigrid linear solver for structural mechanics (2019)
- Hu, Xiaozhe; Lin, Junyuan; Zikatanov, Ludmil T.: An adaptive multigrid method based on path cover (2019)
- Hu, Xiaozhe; Vassilevski, Panayot S.: Modifying AMG coarse spaces with weak approximation property to exhibit approximation in energy Norm (2019)
- Paludetto Magri, Victor A.; Franceschini, Andrea; Janna, Carlo: A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems (2019)
- Fan, Zhou; Guan, Leying: Approximate (\ell_0)-penalized estimation of piecewise-constant signals on graphs (2018)
- 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)
- Kahl, Karsten; Rottmann, Matthias: Least angle regression coarsening in bootstrap algebraic multigrid (2018)
- Monnig, Nathan D.; Meyer, François G.: The resistance perturbation distance: a metric for the analysis of dynamic networks (2018)
- Shaydulin, Ruslan; Safro, Ilya: Aggregative coarsening for multilevel hypergraph partitioning (2018)
- 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)
- Barker, Andrew T.; Lee, Chak S.; Vassilevski, Panayot S.: Spectral upscaling for graph Laplacian problems with application to reservoir simulation (2017)
- Chen, Yannan; Qi, Liqun; Zhang, Xiaoyan: The Fiedler vector of a Laplacian tensor for hypergraph partitioning (2017)
- Fox, Alyson; Manteuffel, Thomas; Sanders, Geoffrey: Numerical methods for Gremban’s expansion of signed graphs (2017)
- Napov, Artem; Notay, Yvan: An efficient multigrid method for graph Laplacian systems. II: Robust aggregation (2017)
- Wegner, Michael; Taubert, Oskar; Schug, Alexander; Meyerhenke, Henning: Maxent-stress optimization of 3D biomolecular models (2017)
- Xu, Jinchao; Zikatanov, Ludmil: Algebraic multigrid methods (2017)
- Hoske, Daniel; Lukarski, Dimitar; Meyerhenke, Henning; Wegner, Michael: Engineering a combinatorial Laplacian solver: lessons learned (2016)