  In this paper we introduce a notion of spectral approximation for directed
graphs. While there are many potential ways one might define approximation for
directed graphs, most of them are too strong to allow sparse approximations in
general. In contrast, we prove that for our notion of approximation, such
sparsifiers do exist, and we show how to compute them in almost linear time.
  Using this notion of approximation, we provide a general framework for
solving asymmetric linear systems that is broadly inspired by the work of
[Peng-Spielman, STOC`14]. Applying this framework in conjunction with our
sparsification algorithm, we obtain an almost linear time algorithm for solving
directed Laplacian systems associated with Eulerian Graphs. Using this solver
in the recent framework of [Cohen-Kelner-Peebles-Peng-Sidford-Vladu, FOCS`16],
we obtain almost linear time algorithms for solving a directed Laplacian linear
system, computing the stationary distribution of a Markov chain, computing
expected commute times in a directed graph, and more.
  For each of these problems, our algorithms improves the previous best running
times of $O((nm^{3/4} + n^{2/3} m) \log^{O(1)} (n \kappa \epsilon^{-1}))$ to
$O((m + n2^{O(\sqrt{\log{n}\log\log{n}})}) \log^{O(1)} (n \kappa
\epsilon^{-1}))$ where $n$ is the number of vertices in the graph, $m$ is the
number of edges, $\kappa$ is a natural condition number associated with the
problem, and $\epsilon$ is the desired accuracy. We hope these results open the
door for further studies into directed spectral graph theory, and will serve as
a stepping stone for designing a new generation of fast algorithms for directed
graphs.
