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 a y such that y - 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 (1990). For any symmetric, weakly diagonally-dominant matrix A with non-positive 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.