CMI Seminar

Tuesday November 27, 2018 4:00 PM

Approximate Gaussian Elimination for Laplacians

Speaker: Rasmus Kyng
Location: Annenberg 314

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm > that approximates a Laplacian matrix by a sparse LU factorization. We compute this factorization by subsampling standard Gaussian elimination. This gives the simplest known nearly linear time solver for Laplacian equations. The crux of our proof is the use of matrix martingales to analyze the algorithm. Finally, we will take a look at ongoing efforts to implement robust and fast Laplacian solvers based on these ideas.

Based on joint work with Sushant Sachdeva and Daniel Spielman.

Series Center for the Mathematics of Information Seminar Series

Contact: Linda Taddeo at 626-395-6704
For more information visit: