Approximate Gaussian elimination and applications

Sushant Sachdeva (UToronto) 09:50 -- 10:30

Gaussian elimination is the best known algorithm for solving systems of linear equations, and one of the oldest algorithms known. However, it is ill-suited for solving sparse systems since even for sparse Laplacian matrices, it can require running time that is super-quadratic in the input size. Several previous approaches speed up Gaussian elimination by introducing error, but fail to provide guarantees. Over the last few years, new versions of approximate Gaussian elimination have been developed for graph Laplacians that provide provable approximation guarantees, and run in time nearly-linear in the sparsity of the graph. In this talk, we will discuss these approaches, and how they lead to 1) simpler nearly-linear time Laplacian solvers, 2) nearly-linear time solvers for systems strictly more general than Laplacians, and 3) faster estimation of all pair effective resistances (which implies faster algorithms for estimating the determinant of a Laplacian).