Nearly linear time algorithms for graph partitioning, graph sparsification, and solving linear systems

Authors: Daniel Spielman and Shang-Hua Teng

Bibliographic Information:

Extended abstract in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 81--90, 2004. Full version available at http://arxiv.org/abs/cs.DS/0310051.

Preliminary experimental results:

Appear in the last slides from the talk that I gave at CMU.

Abstract

We design preconditioners for symmetric diagonally-dominant linear systems that enable their solution in time nearly-linear in their number of non-zero entries. Our algorithm for constructing the preconditioners makes use of two novel algorithmic tools. The first is a nearly-linear time algorithm that takes as input any weighted graph $A$ and outputs a weighted graph $B$ with at most $O (n \log^{O (1)} n)$ edges such that the Laplacian matrices of these graphs, $L_{A}$ and $L_{B}$ satisfy

$$\forall x,\quad x^{T}L_{B}x \leq x^{T} L_{A} x \leq (1+\epsilon ) x^{T}L_{B}x,$$

for any $\epsilon > 0$. In turn, this graph $B$ is obtained from a fast algorithm for the following approximation version of the graph partitioning problem: on input $\phi$ and a graph $G$, output a cut of isoperimetric number at most $O (\phi ^{1/3} \log^{O (1)} n)$ separating at least $2/3$ as many nodes as the best cut of isoperimetric number $\phi$. That is, it attempts to find the most balanced cut of isoperimetric number close to $\phi$. You can download this paper as Postscript, or PDF. This is an improvement of our paper Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^{1.31}) Last modified: Wed May 11 12:52:37 EDT 2005