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 $||{x}-\bar{x}||_A < \epsilon ||\bar{x}||_A $
{$||\cdot||_A$ denotes the A-norm} in time $${\tilde O}(m\log n \log
(1/\epsilon)).$$
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.

提出了一种针对对称对角占优线性系统的改进算法，该算法利用图稀疏化和预处理来构建一条链以求解方程。同时，也介绍了一种构建近似最小 “拉伸” 生成树的算法，并证明了这两个算法的时间效率。