Seminars & Events

Mathematics and Computer Science Division Seminar
"Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver"

DATE: June 6, 2011
TIME: 10:30 AM - 11:30 AM
SPEAKER: Oren Livne, Senior Software Engineer and Research Associate, University of Utah
LOCATION: Building 240 Conference Room 4301, Argonne National Laboratory
HOST: Ilya Safro

Description:
The Laplacian matrices of graphs are large sparse symmetric matrices fundamental to numerous scientific computing problems. In addition to linear algebra and graph-theoretic applications, they arise in classification and machine learning; spectral clustering; dimensionality reduction and data mining; discretization of elliptic partial-differential equations on unstructure grids; interior-point algorithms for transportation network flows; and electrical resistor networks.

We present Lean Algebraic Multigrid (LAMG), a fast solver of the graph Laplacian linear system. LAMG consists of a setup phase that requires O(m) operations, and an iterative solve phase using multigrid cycles, requiring O(m log(1/eps)) operations for eps-accuracy. LAMG is an aggregation-based algebraic multigrid variant that relies on lean, efficient components: caliber-1 interpolation operators, and relaxation-guided aggregation. We also employ a coarse-level energy correction to maintain good asymptotic convergence without excessive fill-in at coarser levels of the multigrid hierarchy.

We present numerical experiments for over 1600 real-world graph instances with up to several millions of nodes and edges. LAMG maintained its optimal efficiency for all those graphs. Although these are preliminary results, to the best of our knowledge LAMG is the first practical linear-scaling solver of the graph Laplacian, and can potentially speed-up the associated computational applications by orders of magnitudes. The developed multiscale methodology can also be extended to non M-matrices and to other computational graph problems.

Save the event to your calendar [schedule.ics]