Source-linked AI summary
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
Rasmus Kyng, Sushant Sachdeva
TL;DR
Solving Laplacian linear systems is a fundamental primitive, but efficient Cholesky factorization faces fill-in. The paper introduces SparseCholesky, a nearly linear-time randomized approach with sparse approximate factors and a new matrix-martingale concentration bound.
Problem
Efficiently solving Laplacian systems matters across theory and practice, while Cholesky factorization faces fill-in from dense cliques created during elimination.
Method
SparseCholesky samples sparse Laplacian approximations to elimination cliques, estimates effective resistances using triangle inequalities, and analyzes the process with bags-of-dice matrix martingales.
Results
O(m log3 n) expected time and O(m log3 n) non-zero entries produce a sparse approximate Cholesky factorization for an n × n Laplacian with m non-zero entries.
Takeaways & Limitations
The solver uses random sampling alone, without graph-theoretic constructions, and provides an analysis contained entirely within the paper.
Takeaways & Limitations
The stated theorem guarantees only expected running time, although a small algorithmic change can provide a different runtime guarantee.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses fill-in that makes exact Cholesky factorization dense, presenting SparseCholesky, a nearly linear-time randomized algorithm with provable approximation guarantees for Laplacians.
- Solving Laplacian systems is a fundamental primitive used in applications including finite elements, graph learning, and maximum-flow algorithms.
- Cholesky factorization enables fast solves, but eliminating variables creates fill-in and can make the factor dense.For Laplacians, eliminating a vertex adds a clique among its neighbors.
- SparseCholesky is the first nearly linear-time algorithm producing a sparse approximate Cholesky decomposition for Laplacian matrices with provable approximation guarantees.
- The algorithm runs in expected time O(m log^3 n) and produces factors with O(m log^3 n) non-zero entries, with the stated high-probability approximation guarantee.
- Using iterative refinement, the approximate factorization solves Laplacian systems in time O(m log^3 n log 1/ε) for zero-sum right-hand sides.
- The analysis randomizes elimination order, estimates effective resistances from unit initial estimates and triangle inequalities, and uses bags-of-dice matrix concentration bounds.
- Unlike prior solvers relying on low-stretch trees, sparsification, or expanders, this algorithm uses purely random sampling and two algebraic Laplacian facts.
2 Preliminaries
The preliminaries define weighted multigraph Laplacians and explain exact Cholesky elimination through Schur complements, whose fill-in forms cliques on eliminated vertices' neighbors.
- Laplacians and Multi-Graphs: A connected undirected weighted multigraph has Laplacian L formed from weighted edge Laplacians, with n vertices and m edges.
- Laplacians and Multi-Graphs: For a connected graph, the Laplacian kernel is the span of the all-ones vector, and L+ denotes its pseudoinverse.
- Cholesky Factorization: Eliminating a variable from Lx = b produces a Schur-complement system on the remaining variables, with the eliminated row and column effectively removed.
- Cholesky Factorization: Sequential elimination selects remaining vertices and records coefficients in a lower-triangular matrix and diagonal matrix, yielding L = PLDL^⊤P^⊤.
- Clique Structure of the Schur Complement: For Laplacians, the Schur complement after eliminating a vertex remains a Laplacian and adds clique edges among that vertex's neighbors.
3 The SparseCholesky Algorithm
SparseCholesky approximates Laplacian elimination while preserving a sparse factorization by sampling the fill-in clique generated at each eliminated vertex. The procedure is nearly linear-time in expectation, with a high-probability runtime variant described separately.
- Guarantees: The main theorem establishes an expected running time of O(m log3 n), while a small modification yields a high-probability runtime bound.The modification restricts random elimination choices to vertices whose multi-edge degree is at most twice the average.
- SparseCholesky: SparseCholesky returns an approximate sparse Cholesky decomposition for a weighted connected graph Laplacian with a stated probability guarantee.The decomposition consists of a permutation, lower-triangular factor, and diagonal matrix.
- Algorithm: The algorithm computes diagonal entries from the current sampled matrix, forms normalized columns, samples the next clique, and assembles the factors through a random permutation.The final output includes the permutation, triangular factor, and diagonal matrix.
- CliqueSample: CliqueSample approximates the clique created by eliminating a vertex using samples of incident multi-edges.Its sampling procedure draws weighted and uniformly selected incident edges to generate sampled edge contributions.
- CliqueSample: CliqueSample adds at most degS(v) multi-edges after eliminating a vertex with degS(v) incident edges, preventing the total multi-edge count from increasing.This directly addresses fill-in, whose clique can contain roughly (degS(v))^2 non-zero entries.
- CliqueSample: CliqueSample runs in O(degS(v)) time, rather than the order (degS(v))^2 time needed to write the eliminated clique explicitly.The procedure only needs the multi-edges incident on the eliminated vertex.
4 Analysis of the Algorithm using Matrix Concentration
This section represents SparseCholesky’s sampling errors as a structured matrix martingale and analyzes them with a new concentration framework. The resulting approximation has expected nearly-linear running time and preserves the input Laplacian within multiplicative error with high probability.
- Martingale construction: SparseCholesky and CliqueSample define a normalized matrix martingale whose increments arise from sampled clique edges during elimination.Conditioned on the elimination choice, the sampled terms are independent and centered.
- Martingale construction: CliqueSample returns samples whose expectation equals the clique created by standard elimination, while each sample is 1/ρ-bounded.These properties connect the sparse approximation to exact Cholesky elimination and support concentration analysis.
- Bags-of-dice concentration: Bags-of-dice martingales formalize the setting where a random bag is selected and its conditionally independent variables are sampled together.This structure matches SparseCholesky because the eliminated vertex determines the bag and the clique samples provide the independent variables.
- Bags-of-dice concentration: Existing matrix concentration bounds are too weak because suitable fixed variance bounds may not exist and the relevant variance can grow large.The paper therefore introduces averaged variance bounds and truncation to control rare large-growth events.
- Algorithmic guarantee: The new concentration theorem yields the multiplicative guarantee (1−ǫ)L ⪯ L(n) ⪯ (1+ǫ)L, while the expected running time is O(mδ^2ǫ^-2 ln^3 n).The final factorization is sparse in expectation and the approximation bound follows from controlling the martingale in both PSD directions.
5 Clique Sampling Proofs
This section proves that CliqueSample efficiently approximates the clique induced by eliminating a vertex. Its samples have the correct expectation, bounded individual contributions, and can be generated in time proportional to the eliminated vertex’s degree.
- CliqueSample guarantees: CliqueSample is used in SparseCholesky to approximate the clique generated when a variable is eliminated.The proof characterizes both the sampling behavior and its computational cost.
- Leverage-score bounds: Effective resistance’s distance property bounds leverage scores for all edges in an elimination clique.This supplies the edge bounds needed to control the sampled clique contributions.
- Implementation: CliqueSample runs in O(degS(v)) time by accessing only edges incident to v and generating O(degS(v)) samples in O(1) time each after preprocessing.Simpler sampling methods would increase the per-sample cost to O(log n), worsening the running time by O(log n).
- Connection to analysis: The expected clique identity allows the sparse approximate Cholesky process to be represented as a martingale.Conditioning on earlier SparseCholesky choices isolates the sampling randomness used in each elimination step.
6 Matrix Concentration Analysis
This section proves the matrix concentration result needed for the algorithm by combining trace-exponential techniques with an inductive analysis of bags-of-dice martingales. The proof controls truncated processes and transfers their concentration bounds to the original martingale.
- Concentration theorem: The main technical result bounds the upper tail of a bags-of-dice matrix martingale using uniform increment and conditional variance controls.The proof establishes the theorem through a sequence of conditional moment-generating-function inequalities.
- Proof framework: Trace exponentials provide the inductive framework for converting conditional matrix moment-generating-function bounds into concentration inequalities.The argument uses Lieb’s concavity theorem and monotonicity of Tr exp under the PSD order.
- Proof framework: The proof chains conditional inequalities across martingale steps and uses auxiliary lemmas to control the resulting exponential terms.The intermediate lemmas establish the required bounds for centered and positive semidefinite random matrices.
- Application: The proof verifies that SparseCholesky’s process is a bags-of-dice martingale because conditional on the elimination choice, its sampled terms are independent and zero mean.This connects the abstract theorem directly to the algorithm’s sampling process.
- Truncation: The truncated martingale is forced to stop when it becomes too large, ensuring boundedness while failing more often than the original process.Concentration of the truncated martingale therefore suffices to establish concentration for the original one.
A Conditions for Bounding Matrix Moment Generating Functions
These lemmas establish operator inequalities for matrix moment-generating functions under bounded centered or positive semidefinite random matrices. They use scalar monotonicity bounds lifted through functional calculus.
- Centered matrices: For a centered symmetric random matrix with norm at most 1, the logarithm of its matrix moment-generating function is bounded using its second moment.The proof applies operator monotonicity of log and log(1+z) ≤ z.
- PSD matrices: For a positive semidefinite random matrix with norm at most 1/3, the logarithm of its moment-generating function is bounded by a multiple of its expectation.The proof uses that g is positive and increasing and that g(1/3) ≤ 6/5.
B Obtaining Concentration of Running Time
The appendix modifies vertex selection to obtain high-probability running-time guarantees while preserving the concentration analysis through degree control and adjusted sampling.
- Theorem B.1 gives LowDegreeSparseCholesky success probability at least 1 − 2/n^δ for connected weighted multigraph Laplacians.
- With high probability, the resulting running time is bounded by O(δ^2 ε^-2 m log^3 n).
- The algorithm samples uniformly among remaining vertices whose degree is at most twice the average degree, with at least half satisfying this condition.Markov's theorem supplies the at-least-half bound, and rejection sampling implements the choice.
- Doubling ρ offsets the factor-two deterioration in the variance bound caused by restricted vertex sampling.
- Rejection sampling adds geometric resampling cost, while CliqueSample calls receive a deterministic per-step bound of O(ρm/(n + 1 − k)).
C Sparse Cholesky Factorization for bDD Matrices
The paper extends approximate sparse Cholesky factorization from Laplacians to bDD matrices using recursive sparsification, while accounting for denser elimination cliques.
- The bDD extension relies on Hermitian spectral approximation and concentration results, but does not factor individual r × r block matrices.
- BDDSparseCholesky runs in O(m log^3 n + n log^5 n) time and produces O(m log^2 n + n log^4 n) non-zeros with high probability.
- The bDD analysis uses a weaker factor-two relation because an effective-resistance distance analogue is unavailable for bDD matrices.
- BDDSparseCholesky adapts LowDegreeSparseCholesky to bDD matrices and recursively invokes Sparsify to control multi-edge growth.
- The bDD clique-sampling routine uses conservative sampling, increasing multi-edge count by at most a factor (1 + 8/n) per elimination.
- After 9·10n eliminations, total multi-edges increase by no more than 2·10^4.
- Recursive sparsification preserves concentration after increasing ρ by a constant and makes recursive computation only a constant fraction of the initial work under an edge-count assumption.
- Its approximate inverse can be applied in O(m log^2 n + n log^4 n) time, and one sparsification pass yields Laplacian factorization time O(m log^2 n log log n) w.h.p.