LAMG 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; BoomerAMG; GitHub; ILUT; hypre; SNAP; AGMG; PyAMG; NetworkX; DIMACS; Trilinos; NetworKit; BootCMatch; PCBDDC; FSAIPACK; CHARMM; ParILUT; CSparse; HSL_MI28; ParMETIS Cited in: 35 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. Zbl 1253.65045Livne, Oren E.; Brandt, Achi 2012 all top 5 Cited by 78 Authors 4 Hu, Xiaozhe 4 Vassilevski, Panayot Spirov 4 Zikatanov, Ludmil T. 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 Meyerhenke, Henning 2 Napov, Artem 2 Paludetto Magri, Victor Antonio 2 Wegner, Michael 2 Wu, Kaiyi 1 An, Hengbin 1 Bagchi, Amitabha 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 Facca, Enrico 1 Fan, Zhou 1 Fika, Paraskevi 1 Fox, Alyson L. 1 Frangioni, Antonio 1 Gelever, Stephan V. 1 Gillani, Iqra Altaf 1 Gottschalk, Hanno 1 Gu, Xianfeng 1 Guan, Leying 1 Hateley, James C. 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 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 Qi, Liqun 1 Rottmann, Matthias 1 Safro, Ilya 1 Sanders, Geoffrey D. 1 Schug, Alexander 1 Serra-Capizzano, Stefano 1 Shaydulin, Ruslan 1 Spiezia, Nicolò 1 Taubert, Oskar 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 all top 5 Cited in 18 Serials 12 SIAM Journal on Scientific Computing 2 Journal of Computational Physics 2 Applied Mathematics and Computation 2 SIAM Journal on Matrix Analysis and Applications 2 ETNA. Electronic Transactions on Numerical Analysis 1 Computer Methods in Applied Mechanics and Engineering 1 Discrete Applied Mathematics 1 The Annals of Statistics 1 Algorithmica 1 Journal of Scientific Computing 1 Linear Algebra and its Applications 1 Numerical Linear Algebra with Applications 1 Acta Mathematica Sinica. English Series 1 Multiscale Modeling & Simulation 1 Acta Numerica 1 SIAM Journal on Imaging Sciences 1 Algorithms 1 SIAM Journal on Mathematics of Data Science all top 5 Cited in 15 Fields 29 Numerical analysis (65-XX) 14 Combinatorics (05-XX) 9 Computer science (68-XX) 5 Statistics (62-XX) 4 Linear and multilinear algebra; matrix theory (15-XX) 3 Operations research, mathematical programming (90-XX) 3 Biology and other natural sciences (92-XX) 2 Probability theory and stochastic processes (60-XX) 2 Optics, electromagnetic theory (78-XX) 1 Ordinary differential equations (34-XX) 1 Partial differential equations (35-XX) 1 Convex and discrete geometry (52-XX) 1 Algebraic topology (55-XX) 1 Manifolds and cell complexes (57-XX) 1 Mechanics of deformable solids (74-XX) Citations by Year