  In this paper, we present a simple combinatorial algorithm that solves
symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It
uses very little of the machinery that previously appeared to be necessary for
a such an algorithm. It does not require recursive preconditioning, spectral
sparsification, or even the Chebyshev Method or Conjugate Gradient. After
constructing a "nice" spanning tree of a graph associated with the linear
system, the entire algorithm consists of the repeated application of a simple
(non-recursive) update rule, which it implements using a lightweight data
structure. The algorithm is numerically stable and can be implemented without
the increased bit-precision required by previous solvers. As such, the
algorithm has the fastest known running time under the standard unit-cost RAM
model. We hope that the simplicity of the algorithm and the insights yielded by
its analysis will be useful in both theory and practice.
