mlsanityData to 7 Oct 2026

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

arXiv 1605.02353 ↗First posted 8 May 2016cs.DScited by 23

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 1; 2023: 3; 2024: 2; 2025: 6; 2026: 8.

23 papers.

Sort:

By area:

  1. 2021SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluationcited by 16
  2. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  3. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  4. 2025The Structural Complexity of Matrix-Vector Multiplicationcited by 4
  5. 2022Towards Neural Sparse Linear Solverscited by 2
  6. 2025Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structurecited by 2
  7. 2026Improved large-scale graph learning through ridge spectral sparsificationcited by 2
  8. 2025SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifoldscited by 1
  9. 2025Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approachcited by 1
  10. 2026Learning Gaussian Graphical Models under Total Positivity via Spectral Graph Sparsificationcited by 1
  11. 2021ℓ2-norm Flow Diffusion in Near-Linear Timecited by 0
  12. 2021Role Similarity Metric Based on Spanning Rooted Forestcited by 0
11 more
  1. 2023Randomized Schur Complement Views for Graph Contrastive Learningcited by 0
  2. 2023Unsupervised Learning via Network-Aware Embeddingscited by 0
  3. 2024Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluationcited by 0
  4. 2025Efficient Sparsification of Simplicial Complexes via Local Densities of Statescited by 0
  5. 2025Graph-based Nearest Neighbors with Dynamic Updates via Random Walkscited by 0
  6. 2026Theoretically and Practically Efficient Resistance Distance Computation on Large Graphscited by 0
  7. 2026Spectral Sparsification of Laplacian-Constrained Gaussian and H"usler-Reiss Graphical Modelscited by 0
  8. 2026Collapsed Effective Operators for Higher-order Structurescited by 0
  9. 2026A Near-Linear-Time Solver for Graph p-Laplacian Semi-Supervised Learning via Continuation in pcited by 0
  10. 2026CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphscited by 0
  11. 2026Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flowcited by 0