swMATH ID: 6551
Software Authors: Livne, Oren E.; Brandt, Achi
Description: 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.
Homepage: http://code.google.com/p/lamg/
Keywords: linear-scaling numerical linear solver; numerical examples; lean algebraic multigrid solver; symmetric linear system; graph Laplacian; piecewise-constant interpolation; convergence; eigenproblems; graph computation
Related Software: SparseMatrix; GitHub; BoomerAMG; ILUT; NetworKit; hypre; SNAP; AGMG; Eigen; PyAMG; Laplacians.jl; NetworkX; DIMACS; Trilinos; BootCMatch; PCBDDC; FSAIPACK; PyTorch; DeepSDF; Cityscapes
Cited in: 39 Documents
all top 5

Cited by 92 Authors

4 Hu, Xiaozhe
4 Vassilevski, Panayot Spirov
3 Meyerhenke, Henning
3 Notay, Yvan
2 Adrian, Simon B.
2 Andriulli, Francesco P.
2 Barker, Andrew T.
2 Benzi, Michele
2 Eibert, Thomas F.
2 Franceschini, Andrea
2 Janna, Carlo
2 Kahl, Karsten
2 Lee, Chak Shing
2 Napov, Artem
2 Paludetto Magri, Victor Antonio
2 Serra-Capizzano, Stefano
2 Wegner, Michael
2 Wu, Kaiyi
2 Zikatanov, Ludmil T.
1 Adriani, Andrea
1 An, Hengbin
1 Angriman, Eugenio
1 Bagchi, Amitabha
1 Bianchi, Davide
1 Biros, George
1 Brandt, Achi E.
1 Chen, Chao
1 Chen, Long
1 Chen, Yannan
1 Choi, Gary Pui-Tung
1 Cowen, Lenore J.
1 Dell’Acqua, Pietro
1 Devkota, Kapil
1 Eliasof, Moshe
1 Ephrath, Jonathan
1 Facca, Enrico
1 Fan, Zhou
1 Ferrari, Paola
1 Fika, Paraskevi
1 Fox, Alyson L.
1 Frangioni, Antonio
1 Gelever, Stephan V.
1 Gillani, Iqra Altaf
1 Görtz, Morgan
1 Gottschalk, Hanno
1 Gu, Xianfeng
1 Guan, Leying
1 Hateley, James C.
1 Hellman, Fredrik
1 Hoske, Daniel
1 Hou, Thomas Yizhao
1 Huang, De
1 Lam, Ka Chun
1 Leung-Liu, Yusan
1 Liang, Tianyu
1 Lin, Junyuan
1 Liu, Jian
1 Livne, Oren E.
1 Lui, Lok Ming
1 Lukarski, Dimitar
1 Målqvist, Axel
1 Manteuffel, Thomas A.
1 Mazzucco, Gianluca
1 Meyer, François G.
1 Mitrouli, Marilena
1 Monnig, Nathan D.
1 Murphy, James M.
1 Osborn, Sarah V.
1 Predari, Maria
1 Qi, Liqun
1 Rottmann, Matthias
1 Ruthotto, Lars
1 Safro, Ilya
1 Sanders, Geoffrey D.
1 Schug, Alexander
1 Shaydulin, Ruslan
1 Spiezia, Nicolò
1 Taubert, Oskar
1 Treister, Eran
1 van der Grinten, Alexander
1 Wei, Guowei
1 Wei, Huayi
1 Wu, Jie
1 Xia, Kelin
1 Xu, Jinchao
1 Xu, Xiaowen
1 Xu, Xinhai
1 Yang, Xuejun
1 Yau, Stephen Shing-Toung
1 Ye, Shuai
1 Zhang, Pengchuan
1 Zhang, Xiaoyan

Citations by Year