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 $\mathcal{ T}_{ \rm S}(m)$ to output a sparsifier with $\mathcal{ N}_{ \rm S}(n)$ edges, our algorithm solves a directed Eulerian system on $n$ vertices and $m$ edges to $\epsilon$ relative accuracy in time $$ O(\mathcal{ T}_{ \rm S}(m) + { \mathcal{ N}_{ \rm S}(n)\log { n}\log(n/\epsilon)}) + \tilde{ O}(\mathcal{ T}_{ \rm S}(\mathcal{ N}_{ \rm S}(n)) \log n), $$ where the $\tilde{ O}(\cdot)$ notation hides $\log\log(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 \log^{ 5}n \log(n / \epsilon))$ time after $O(n^2 \log^{ O(1)} n)$ pre-processing. At the core of our analyses are constructions of augmented matrices whose Schur complements encode error matrices.
Categories: cs.DS