Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

We present a randomized algorithm that on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b produces an x such that \|x - A^ b \|₀ \|A^ b\|₀ in expected time O (m ^cn (1/) ) for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya in 1990. For any symmetric, weakly diagonally dominant matrix A with nonpositive off-diagonal entries and k 1, we construct in time O (m ^c n) a preconditioner B of A with at most 2 (n - 1) + O ( (m/k) ^39 n) nonzero off-diagonal entries such that the finite generalized condition number ₅ (A, B) is at most k, for some other constant c. In the special case when the nonzero structure of the matrix is planar the corresponding linear system solver runs in expected time O (n ^2 n + n n \ n \ (1/) ). We hope that our introduction of algorithms of low asymptotic complexity will lead to the development of algorithms that are also fast in practice.