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

arXiv: https://arxiv.org/abs/1301.6628 · HTML: https://mlsanity.com/paper/1301.6628/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2013.

## Built on by (most cited first, 2 of 2)

- [HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks](https://mlsanity.com/paper/2403.18142/) (2024)
- [Efficient Sparsification of Simplicial Complexes via Local Densities of States](https://mlsanity.com/paper/2502.07558/) (2025)

## Abstract (arXiv)

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.