Richard Peng: Algorithm Design using Spectral Graph Theory

Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.

This talk will present the first parallel algorithm for solving linear systems in graph Laplacians that runs in polylogarithmic time and nearly-linear work. The heart of the algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving these systems of equations rely on tree embeddings, this algorithm only requires constructing spectrally similar graphs. This is joint work with Dan Spielman.

The first half of this talk will also survey two decades of progress in combinatorial preconditioning, which combines numerical and combinatorial algorithms via spectral graph theory.