Approaching optimality for solving SDD systems

We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\widehat{G}$ with $n-1+m\mathrm{/}k$ edges, such that the condition number of $G$ with $\widehat{G}$ is bounded above by $\tilde{O}(k{\log }^{2}n)$, with probability $1-p$. The algorithm runs in time $$\tilde{O}((m\log n+n{\log }^{2}n)\log (1\mathrm{/}p))\mathrm{.}$$ As a result, we obtain an algorithm that on input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$, computes a vector $x$ satisfying $\mathrm{\mid }\mathrm{\mid }x-A^{+}b\mathrm{\mid }{\mathrm{\mid }}_A<ϵ\mathrm{\mid }\mathrm{\mid }{A}^{+}b\mathrm{\mid }{\mathrm{\mid }}_A$, in expected time $$\tilde{O}(m{\log }^{2}n\log (1\mathrm{/}ϵ))\mathrm{.}$$ 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.