A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time

Understand

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.