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.

Surveys, Classes, and Expository Articles

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 following are some of the foundational papers of the field:

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", (SICOMP 2013)
  2. "Spectral Sparsification of Graphs", (SICOMP 2011) and
  3. "Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems". (SIMAX 2014)
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

Improved Solvers


The asymptotically fastest known solver appears in the following two papers
The simplest fast solver appears in the paper: 
This may be viewed as an improvement of the solver in the paper:
The algorithm of the later paper is faster asymptotically, but a little too complicated to really implement.

Another simple approach to solving these systems appears in the papers:
The simplest algorithms based on augmented spanning tree preconditioners appear in the papers:
These papers find efficient (and incredibly simple) ways to construct the precondtioners whose existance was first proved in:
Efficient parallel algorithms that only depend on sparsification may be found in these papers:

Solvers for Directed (non-symmetric) Laplacians

A recent breakthrough in the solution of non-symmetric systems in the Laplacian matrices of directed graphs appears in the following two papers (with more to come):

Code


Laplacians.jl is a package that implements many algorithms discussed in these papers.

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 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 of Laplacian matrices may be found in the following papers.
Approaches to spectral sparsification of arbitrary matrices appear in these two papers:

Uses of Laplacian solvers inside Interior-Point Methods


Some other support-theory based algorithms


Mathematical foundations of combinatorial preconditioning