Approaching Optimality for Solving SDD Linear Systems

Abstract

We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k, produces an incremental sparsifier G with n-1+m/k edges, such that the condition number of G with G is bounded above by Õ(k log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n), with probability 1-p. The algorithm runs in time Õ((m log n + n log n) log(1/p)). As a result, we obtain an algorithm that on input of an n × n symmetric diagonally dominant matrix A with m non-zero entries and a vector b, computes a vector x satisfying ||x-A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> b||A <; ϵ||A <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> b||A, in expected time Õ(m log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n log(1/ϵ)). The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.