Sparsified Block Elimination for Directed Laplacians

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 Trm S(m) to output a sparsifier with Nrm S(n) edges, our algorithm solves a directed Eulerian system on n vertices and m edges to ε relative accuracy in time O(Trm S(m) + Nrm S(n)log nlog(n/ε)) + tildeO(Trm S(Nrm S(n)) log n), where the tildeO(·) notation hides loglog(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 log5n log(n / ε)) time after O(n2 logO(1) n) pre-processing. At the core of our analyses are constructions of augmented matrices whose Schur complements encode error matrices.