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

Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4

We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an $n\times n$ Eulerian directed Laplacian with $m$ nonzero entries, we show how to…