ShangHua 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 graphtheoretic 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 PreconditioningThe 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 SpielmanTeng PapersShangHua Teng and I wrote a large paper on this topic, "NearlyLinear 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, diagonallydominant linear sytems in nearlylinear 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.
Improved SolversThe 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.
Efficient parallel algorithms that only depend on sparsification may be found in these papers:
Solvers for Directed (nonsymmetric) Laplacians
CodeLaplacians.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 diagonallydominant 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 ClusteringThe 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:
Low Stretch Spanning Trees
SparsificationImprovements 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 InteriorPoint Methods
Some other supporttheory based algorithms
Mathematical foundations of combinatorial preconditioning
