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 bA ≤ εA bA in expected time O (m logᶜn log (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 logᶜ n) a preconditioner B of A with at most 2 (n - 1) + O ((m/k) log³⁹ n) nonzero off-diagonal entries such that the finite generalized condition number κf (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 log² n + n log n \ log log n \ log (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.