Solving sparse, symmetric, diagonally-dominant linear systems in time O(m/sup 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 b, produces a vector x/spl tilde/ within relative distance /spl epsi/ of the solution to Ax = b in time O(m/sup 1.31/log(n//spl epsi/)b/sup O(1)/), where b is the log of the ratio of the largest to smallest non-zero entry of A. If the graph of A has genus m/sup 2/spl theta// or does not have a K/sub m/spl theta// minor, then the exponent of m can be improved to the minimum of 1 + 5/spl theta/ and (9/8)(1 + /spl theta/). The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.