# Sparsified Block Elimination for Directed Laplacians

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Nov 2021.

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

- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)

## Abstract (arXiv)

We show that the sparsified block elimination algorithm for solving undirected Laplacian linear systems from [Kyng-Lee-Peng-Sachdeva-Spielman STOC'16] directly works for directed Laplacians. Given access to a sparsification algorithm that, on graphs with n vertices and m edges, takes time Trm S(m) to output a sparsifier with Nrm S(n) edges, our algorithm solves a directed Eulerian system on n vertices and m edges to ε relative accuracy in time  O(Trm S(m) + Nrm S(n)log nlog(n/ε)) + tildeO(Trm S(Nrm S(n)) log n),  where the tildeO(·) notation hides loglog(n) factors. By previous results, this implies improved runtimes for linear systems in strongly connected directed graphs, PageRank matrices, and asymmetric M-matrices. When combined with slower constructions of smaller Eulerian sparsifiers based on short cycle decompositions, it also gives a solver that runs in O(n log5n log(n / ε)) time after O(n2 logO(1) n) pre-processing. At the core of our analyses are constructions of augmented matrices whose Schur complements encode error matrices.