Abstract

We will survey a sparsification based approach for designing algorithms for structured matrices. These algorithms accelerate numerical routines by sampling the nonzero entries of the dense intermediate matrices, leading to only sparse matrices in all intermediate steps.

This framework leads provably nearly-linear time and polylog depth algorithms for solving linear systems and computing matrix roots of graph Laplacians. These matrices, as well as their extensions to M matrices and connection Laplacians, have a wide range of applications in combinatorial optimization, machine learning, scientific computing, and image processing.

At the core of these algorithms are efficient methods for computing sparse approximations to random walks and Schur complements, which may be of independent interest.

This survey is based on works joint with Dehua Cheng, Yu Cheng, Rasmus Kyng, Yin Tat Lee, Yan Liu, Sushant Sachdeva, Daniel Spielman, and Shang-Hua Teng, available on arXiv as 1311.3286, 1410.5392,1502.03496, 1512.01892.

Time

Speaker

Room