# Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2016.

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

- [SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluation](https://mlsanity.com/paper/2102.03716/) (2021)
- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [Towards Neural Sparse Linear Solvers](https://mlsanity.com/paper/2203.06944/) (2022)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifolds](https://mlsanity.com/paper/2508.18306/) (2025)
- [Improved large-scale graph learning through ridge spectral sparsification](https://mlsanity.com/paper/2604.20078/) (2026)
- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsification](https://mlsanity.com/paper/2605.17154/) (2026)
- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Role Similarity Metric Based on Spanning Rooted Forest](https://mlsanity.com/paper/2110.07872/) (2021)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [Unsupervised Learning via Network-Aware Embeddings](https://mlsanity.com/paper/2309.10408/) (2023)
- [Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation](https://mlsanity.com/paper/2401.15615/) (2024)
- [Efficient Sparsification of Simplicial Complexes via Local Densities of States](https://mlsanity.com/paper/2502.07558/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)
- [Spectral Sparsification of Laplacian-Constrained Gaussian and H"usler-Reiss Graphical Models](https://mlsanity.com/paper/2606.16681/) (2026)
- [Collapsed Effective Operators for Higher-order Structures](https://mlsanity.com/paper/2606.23517/) (2026)
- [A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in p](https://mlsanity.com/paper/2607.03503/) (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)

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization, the version of Gaussian elimination for symmetric matrices. This is the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our analysis is a novel concentration bound for matrix martingales where the differences are sums of conditionally independent variables.