Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O (m^1. 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 (m^1. 31 (n κ₅ (A) /ε) ^O (1) ), where κ₅ (A) is the log of the ratio of the largest to smallest non-zero eigenvalue of A. In particular, (κ₅ (A) ) = O (b 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θ or does not have a K₌^⏗ 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.