  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 compute an $\epsilon$-approximate solution in time $O(m
\log^{O(1)} (n) \log (1/\epsilon))$. Through reductions from [Cohen et al.
FOCS'16] , this gives the first nearly-linear time algorithms for computing
$\epsilon$-approximate solutions to row or column diagonally dominant linear
systems (including arbitrary directed Laplacians) and computing
$\epsilon$-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(\sqrt{\log n \log \log
n})})\log^{O(1)}(n \epsilon^{-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 $ {\mathbf{L}}$, there is a lower triangular matrix
$\boldsymbol{\mathit{{\mathfrak{L}}}}$ and an upper triangular matrix
$\boldsymbol{\mathit{{\mathfrak{U}}}}$, each with at most $\tilde{O}(n)$
nonzero entries, such that their product $\boldsymbol{\mathit{{\mathfrak{L}}}}
\boldsymbol{\mathit{{\mathfrak{U}}}}$ spectrally approximates $ {\mathbf{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.
