  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} $\hat{G}$
with $n-1 + m/k$ edges, such that the condition number of $G$ with $\hat{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/p)).$$
  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 $||{x}-A^{+}b||_A<\epsilon ||A^{+}b||_A $,
in expected time
  $$\tilde{O}(m\log^2{n}\log(1/\epsilon)).$$
  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.
