[Colloquium] Seminar Announcement: Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver - TODAY!

[Ninfa Mayorga]

Computation Institute- Data Lunch Seminar (DLS)

Speaker: Oren Livne,Senior Software Engineer, University of Utah
Date: June 10, 2011
Time: 12:00 PM - 1:00 PM
Location: University of Chicago, Searle 240A, 5735 S. Ellis Avenue

Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver

Abstract:
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.

Joint work with Professor Achi Brandt, Weizmann Institute of Science.

Bio:
Oren Livne is the senior software engineer of the FURTHeR project at  
the Clinical Translational and Science Award program at the University  
of Utah. He received his Bachelor's degree from the Technion in 1994,  
and his Ph.D. degree from the Weizmann Institute of Science in 2000,  
both in applied mathematics. He was a postdoctoral fellow at Stanford  
University and the University of Utah from 2002 to 2004. After working  
as a computational scientist at the Israeli Aircraft Industries and  
Orbotech, Inc., Oren was the chief software architect of The RUReady  
Program and RUReady, Inc. prior to joining FURTHeR in 2008. He has 35  
scholarly publications, a pending patent, and is a co-author of the  
new book "Multigrid Guide" (SIAM, 2011) with his former Ph.D. advisor,  
Achi Brandt.

Information: Lunch will be provided