Laplacian Linear Equations,

Graph Sparsification, Local Clustering, Low-Stretch Trees, etc.


Shang-Hua Teng and I wrote a large paper on the problem of solving systems of linear equations in the Laplacian matrices of graphs.
This paper required many graph-theoretic algorithms, most of which have been greatly improved.  This page is an attempt to keep
track of the major developments in and applications of these ideas.

Combinatorial Preconditioning

The combinatorial approach to preconditioning, also called support theory, was introduced by Vaidya in an unpublished paper.  For more information on the history of this field, I recommend Bruce Hendrickson's Support Theory for Preconditioning page.

The Spielman-Teng Papers

Shang-Hua Teng and I wrote a large paper on this topic, "Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification and Solving Linear Systems", (prelim version in STOC '04, extended version on arxiv), in which we showed how to solve symmetric, diagonally-dominant linear sytems in nearly-linear time.  We have since broken that paper into three papers, each of which may be read on its own, and which have been submitted to journals individually.
  1. "A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning",
  2. "Spectral Sparsification of Graphs", (SICOMP 2011) and
  3. "Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems".
Expositions of the content of these papers may be found in the tutorial I gave at IPCO05 (here are the slides) and in some of the lectures of my classes Spectral Graph Theory and its Applications. and Spectral Graph Theory

The Best Solvers

Presently, the best constructions of combinatorial preconditioners appear in the papers:
These papers find efficient (and incredibly simple) ways to construct the precondtioners
whose existance was first proved in:

Code

Yiannis Koutis has written code that implements a version of combinatorial preconditiong.  You can find it here.

An implementation of Vaidya's original approach is implemented in the TAUCS package, written by Doron Chen, Vladimir Rotkin and Sivan Toledo.

If you need to solve diagonally-dominant linear systems, I also suggest trying the Algebraic Multigrid algorithm.
You can find an implementation in the LAMG package, written by Oren Livne.

Local Graph Clustering

The problem of local graph clustering was introduced in paper number 1 above.
Given a massive graph and a vertex of interest, the problem is to find a cluster in the graph around the given vertex.
Moreover, we try to do this in time proportional to the size of the cluster returned.  Algorithms for this problem are
useful for two reasons.  The first is that they are very efficient as they can ignore most of the graph.  The second is
that they provide one of the few ways of identifying small clusters in certain regions.

Our paper has been substantially improved in the following three papers:
Algorithms from these papers have been used in a large number of clustering applications.  Here are some examples.

Low-Stretch Spanning Trees


Sparsification

Improvements in spectral sparsification may be found in the following papers.

Other support-theory based algorithms


Mathematical foundations of combinatorial preconditioning