Approaching optimality for solving sdd linear systems

We present an algorithm that on input of an n-vertex m-edge weighted graph G and a value k produces an incremental sparsifier Ĝ with n-1+m/k edges, such that the relative condition number of G with Ĝ is bounded above by Õ(k log² n), with probability 1-p (we use the Õ() notation to hide a factor of at most (log log n)⁴). The algorithm runs in time Õ((mlog 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 nonzero entries and a vector b computes a vector x satisfying ||x-A+b||A <ε|A+b||A, in expected time Õ(mlog² 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 the recursive preconditioned Chebyshev iteration.