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.
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:
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.
The fastest known solver appears in the following two papers
The simplest truly fast solver for Laplacian (and SDD) systems appears in the papers
whose existance was first proved in:
Efficient parallel algorithms that only depend on sparsification may be found in these papers:
Algorithms based on sparsifying Cholesky factorization appear in these papers:
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.
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:
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: