Search Mailing List Archives
[theory-seminar] Theory Seminar on Thursday
Shashwat Silas
silas at stanford.edu
Tue Oct 17 13:46:42 PDT 2017
Hi All,
There will be a theory seminar on Thursday at 415pm in Gates 463A. Hope to see you there!
Rasmus Kyng (Simons)
Approximate Gaussian Elimination for Laplacians
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 matrix with 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. It is a significant step towards practical and provably correct algorithms for this problem. The crux of our proof is the use of matrix martingales to analyze the algorithm.
Joint work with Sushant Sachdeva.
Thanks,
Shashwat
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20171017/6d1fa343/attachment.html>
More information about the theory-seminar
mailing list