Linear Algebraic Primitives Beyond Laplacian Solvers

Aaron Sidford (Stanford) 09:10 -- 09:50

Over the past decade nearly linear time Laplacian system solving has emerged as powerful algorithmic hammer in improving asymptotic running times of solving a wide variety of problems. Both the black-box application of Laplacian system solvers and the application of the algorithmic techniques underlying recent efficient Laplacian system solving algorithms have had broad implications in algorithm design. In this talk I will discuss recent progress in advancing this machinery beyond solving Laplacians systems towards solving broader classes of structured linear systems in nearly linear time. This talk will focus on recent advances in solving directed Laplacians (and more broadly M-matrices) in nearly linear time through efficient reductions to solving row-column diagonally dominant (RCDD) systems. Further, this talk will connect these problems to a variety of closely related linear algebraic problems including PageRank computation, policy evaluation, stationary distribution computation, Perron-Vectors computation, and more.