Theory Seminar

Friday, December 2, 2016 -
4:00pm to 5:00pm


ASA Conference Room 6115 Gates & Hillman Centers


RASMUS KYNG, Ph.D. Student

Event Website:

For More Information, Contact:

We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Choleskyfactorization – the version of Gaussian elimination for positive semi-definite matrices. We compute this factorization by subsampling standard Gaussian elimination.This is the first nearly linear time solver for Laplaciansystems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our proof is the use of matrix martingales to analyze the algorithm. Joint work with Sushant Sachdeva.


Seminar Series