REVIEW 2 cited by
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
read the original abstract
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.
Forward citations
Cited by 2 Pith papers
-
Flows in Almost Linear Time via Adaptive Preconditioning
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
-
Improved large-scale graph learning through ridge spectral sparsification
GSQUEAK produces spectrally accurate sparsifiers for graph Laplacians in a single-pass distributed streaming setting.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.