Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^{1.31})

Authors: Daniel A. Spielman and Shang-Hua Teng

Bibliographic Information: To appear in the Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science.

Abstract

We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $b$, produces a vector $\tilde{x}$ within relative distance $\epsilon$ of the solution to $A x = b$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon )^{O (1)} )$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{f} (A)) = O (b \log n)$, where $b$ is the logarithm of the ratio of the largest to smallest non-zero entry of $A$. If the graph of $A$ has genus $m^{2\theta }$ or does not have a $K_{m^{\theta }}$ minor, then the exponent of $m$ can be improved to the minimum of $1 + 5 \theta$ and $(9/8) (1+\theta )$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.

You can download the current version of the paper in Postscript or PDF.
This version includes proofs that were omitted from the FOCS version, and cleans up some numerical details. You can also download the FOCS version in Postscript or PDF. Last modified: Wed Mar 31 17:36:01 EST 2004