2011/08/05 by Oren E. Livne, Livne, Oren E., Achi Brandt +1 · 5 citations
Computer Science · Physics and Astronomy · #05C50 #65F10 #65F50 #65M55 #68R10 #90C06 #90C35 #Complex Network Analysis Techniques #F.2.1 #FOS: Mathematics #G.1.3 #G.1.8 #G.2.2 #G.2.3 #Graph Theory and Algorithms #Matrix Theory and Algorithms #Numerical Analysis (math.NA)
paper · pdf · doi:10.48550/arxiv.1108.1310
openalex publication_date 2011/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Laplacian matrices of graphs arise in large-scale computational applications\nsuch as semi-supervised machine learning; spectral clustering of images,\ngenetic data and web pages; transportation network flows; electrical resistor\ncircuits; and elliptic partial differential equations discretized on\nunstructured grids with finite elements. A Lean Algebraic Multigrid (LAMG)\nsolver of the symmetric linear system Ax=b is presented, where A is a graph\nLaplacian. LAMG's run time and storage are empirically demonstrated to scale\nlinearly with the number of edges.\n LAMG consists of a setup phase during which a sequence of\nincreasingly-coarser Laplacian systems is constructed, and an iterative solve\nphase using multigrid cycles. General graphs pose algorithmic challenges not\nencountered in traditional multigrid applications. LAMG combines a lean\npiecewise-constant interpolation, judicious node aggregation based on a new\nnode proximity measure (the affinity), and an energy correction of coarse-level\nsystems. This results in fast convergence and substantial setup and memory\nsavings. A serial LAMG implementation scaled linearly for a diverse set of 3774\nreal-world graphs with up to 47 million edges, with no parameter tuning. LAMG\nwas more robust than the UMFPACK direct solver and Combinatorial Multigrid\n(CMG), although CMG was faster than LAMG on average. Our methodology is\nextensible to eigenproblems and other graph computations.\n