A nearly-mlogn time solver for SDD linear systems

We present an improved algorithm for solving symmetrically diagonally dominant linear systems. On input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$ such that $A\bar{x}=b$ for some (unknown) vector $\bar{x}$, our algorithm computes a vector $x$ such that $\mathrm{\mid }\mathrm{\mid }x-\bar{x}\mathrm{\mid }{\mathrm{\mid }}_A<ϵ\mathrm{\mid }\mathrm{\mid }\bar{x}\mathrm{\mid }{\mathrm{\mid }}_A$ {$\mathrm{\mid }\mathrm{\mid }\cdot \mathrm{\mid }{\mathrm{\mid }}_A$ denotes the A-norm} in time $$\tilde{O}(m\log n\log (1\mathrm{/}ϵ))\mathrm{.}$$ The solver utilizes in a standard way a `preconditioning’ chain of progressively sparser graphs. To claim the faster running time we make a two-fold improvement in the algorithm for constructing the chain. The new chain exploits previously unknown properties of the graph sparsification algorithm given in [Koutis,Miller,Peng, FOCS 2010], allowing for stronger preconditioning properties. We also present an algorithm of independent interest that constructs nearly-tight low-stretch spanning trees in time $\tilde{O}(m\log n)$, a factor of $O(\log n)$ faster than the algorithm in [Abraham,Bartal,Neiman, FOCS 2008]. This speedup directly reflects on the construction time of the preconditioning chain.