Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m1.31)

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 , produces a vector within relative distance $ε$ of the solution to A = in time O (m1.31 log (n κf (A)/ε)O (1)), where κf (A) is the log of the ratio of the largest to smallest non-zero eigenvalue of A. In particular, log (κ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 m2θ or does not have a Km^θ minor, then the exponent of m can be improved to the minimum of $1 + 5 θ$ and $(9/8) (1+θ)$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.