# Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2020.

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

- [Understanding Oversquashing in GNNs through the Lens of Effective Resistance](https://mlsanity.com/paper/2302.06835/) (2023)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Understanding Truncated Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2606.13671/) (2026)
- [CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs](https://mlsanity.com/paper/2609.09255/) (2026)
- [Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow](https://mlsanity.com/paper/2609.09295/) (2026)

## Abstract (arXiv)

In this paper we provide an O(m (log log n)O(1) log(1/ε))-expected time algorithm for solving Laplacian systems on n-node m-edge graphs, improving improving upon the previous best expected runtime of O(m √log n (log log n)O(1) log(1/ε)) achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of ℓp-stretch graph approximations with improved stretch and sparsity bounds. Additionally, as motivation for this work, we show that for every set of vectors in ℝd (not just those induced by graphs) and all k > 1 there exist ultrasparsifiers with d-1 + O(d/√k) re-weighted vectors of relative condition number at most k. For small k, this improves upon the previous best known relative condition number of tildeO(√k log d), which is only known for the graph case.