# Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2018.

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

- [Solving Dense Linear Systems Faster Than via Preconditioning](https://mlsanity.com/paper/2312.08893/) (2023)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure](https://mlsanity.com/paper/2507.11724/) (2025)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model](https://mlsanity.com/paper/2509.13112/) (2025)
- [Fast, Parallel, Query-Efficient Binary Classification](https://mlsanity.com/paper/2607.04062/) (2026)

## Abstract (arXiv)

We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an n × n Eulerian directed Laplacian with m nonzero entries, we show how to compute an ε-approximate solution in time O(m logO(1) (n) log (1/ε)). Through reductions from [Cohen et al. FOCS'16] , this gives the first nearly-linear time algorithms for computing ε-approximate solutions to row or column diagonally dominant linear systems (including arbitrary directed Laplacians) and computing ε-approximations to various properties of random walks on directed graphs, including stationary distributions, personalized PageRank vectors, hitting times, and escape probabilities. These bounds improve upon the recent almost-linear algorithms of [Cohen et al. STOC'17], which gave an algorithm to solve Eulerian Laplacian systems in time O((m+n2^O(√log n log log n))logO(1)(n ε-1)). To achieve our results, we provide a structural result that we believe is of independent interest. We show that Laplacians of all strongly connected directed graphs have sparse approximate LU-factorizations. That is, for every such directed Laplacian  L, there is a lower triangular matrix boldsymbolmathitmathfrakL and an upper triangular matrix boldsymbolmathitmathfrakU, each with at most tildeO(n) nonzero entries, such that their product boldsymbolmathitmathfrakL boldsymbolmathitmathfrakU spectrally approximates  L in an appropriate norm. This claim can be viewed as an analogue of recent work on sparse Cholesky factorizations of Laplacians of undirected graphs. We show how to construct such factorizations in nearly-linear time and prove that, once constructed, they yield nearly-linear time algorithms for solving directed Laplacian systems.