# An Efficient Parallel Solver for SDD Linear Systems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2013.

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

- [Graph Transformers Dream of Electric Flow](https://mlsanity.com/paper/2410.16699/) (2024)
- [HERTA: A High-Efficiency and Rigorous Training Algorithm for Unfolded Graph Neural Networks](https://mlsanity.com/paper/2403.18142/) (2024)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)

## Abstract (arXiv)

We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.