# Robust and Practical Solution of Laplacian Equations by Approximate Elimination

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2023.

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

- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Efficient Algorithms for Computing Random Walk Centrality](https://mlsanity.com/paper/2510.20604/) (2025)
- [Promoting Fairness in Information Access within Social Networks](https://mlsanity.com/paper/2512.14711/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)
- [Support Discovery With Iteratively Reweighted Least Squares for Fixed-Charge Network Flow](https://mlsanity.com/paper/2609.09295/) (2026)
- [Scaffold: Support Graph Theory Based Sparsification for Graph Neural Networks](https://mlsanity.com/paper/2609.31466/) (2026)

## Abstract (arXiv)

We introduce a new algorithm and software for solving linear equations in symmetric diagonally dominant matrices with non-positive off-diagonal entries (SDDM matrices), including Laplacian matrices. We use pre-conditioned conjugate gradient (PCG) to solve the system of linear equations. Our preconditioner is a variant of the Approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016). Our factorization approach is simple: we eliminate matrix rows/columns one at a time and update the remaining matrix using sampling to approximate the outcome of complete Cholesky factorization. Unlike earlier approaches, our sampling always maintains a connectivity in the remaining non-zero structure. Our algorithm comes with a tuning parameter that upper bounds the number of samples made per original entry. We implement our algorithm in Julia, providing two versions, AC and AC2, that respectively use 1 and 2 samples per original entry. We compare their single-threaded performance to that of current state-of-the-art solvers Combinatorial Multigrid (CMG), BoomerAMG-preconditioned Krylov solvers from HyPre and PETSc, Lean Algebraic Multigrid (LAMG), and MATLAB's with Incomplete Cholesky Factorization (ICC). Our evaluation uses a broad class of problems, including all large SDDM matrices from the SuiteSparse collection and diverse programmatically generated instances. Our experiments suggest that our algorithm attains a level of robustness and reliability not seen before in SDDM solvers, while retaining good performance across all instances. Our code and data are public, and we provide a tutorial on how to replicate our tests. We hope that others will adopt this suite of tests as a benchmark, which we refer to as SDDM2023. Our solver code is available at: https://github.com/danspielman/Laplacians.jl/ Our benchmarking data and tutorial are available at: https://rjkyng.github.io/SDDM2023/