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

Mathematics – Numerical Analysis

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

23 pages. Manuscript submitted to SISC on August 5, 2011. arXiv admin note: substantial text overlap with arXiv:1108.0123

Scientific paper

Laplacian matrices of graphs arise in large-scale computational applications such as 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 linear in the number of graph edges. It is robust and requires no fine tuning. LAMG consists of a setup phase, in 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 applications of algebraic multigrid. LAMG combines a lean piecewise-constant interpolation, judicious node aggregation based on a new node proximity definition, and a novel energy correction of the coarse-level systems. This results in fast convergence and substantial overhead and memory savings. A serial LAMG implementation scaled linearly for a diverse set of 1666 real-world graphs with up to six million edges. This multilevel methodology can be fully parallelized and extended to eigenvalue problems and other graph computations.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver (Journal Version) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver (Journal Version), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver (Journal Version) will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-668458

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.