Solvers for Directed Laplacian Systems

This talk will overview algorithms for solving linear systems associated with random walks on directed graphs. Two key components in these algorithms are: (1) the interplay between stationary distributions and Eulerian rescalings that narrow the ratios between in- and out- weighted degrees; (2) efficient sparsified squaring / elimination routines for Eulerian Laplacian matrices. Connections with spectral approximations of asymmetric matrices, as well as bit complexity, will also be mentioned.