#
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 -by- symmetric positive semi-definite, diagonally dominant
matrix with non-zero entries and an -vector ,
produces a vector within relative distance
of the solution to
in time
,
where
is the log of the ratio of the largest to smallest non-zero
eigenvalue of .
In particular,
, where
is the logarithm of the ratio of the largest to smallest
non-zero entry of .
If the graph of has genus
or does not have a
minor,
then the exponent of can be improved to
the minimum of
and
.
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.

Daniel A. Spielman
Last modified: Wed Mar 31 17:36:01 EST 2004