<div dir="ltr"><br>Hi Everyone,<br><br>This Friday in the YPNG seminar Rasmus Kyng will talk about:<br><br>Title: Approximate Gaussian Elimination for Laplacians<br><br>Abstract: We show how to perform sparse approximate Gaussian elimination for <br>Laplacian matrices. We present a simple, nearly linear time algorithm that approximates <br>a Laplacian by a matrix with a sparse Cholesky factorization – the version of Gaussian <br>elimination for positive semi-definite matrices. We compute this factorization by <br>subsampling standard Gaussian elimination. This is the first nearly linear time solver <br>for Laplacian systems that is based purely on random sampling, and does not use <br>any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. <br>The crux of our proof is the use of matrix martingales to analyze the algorithm.  <br>Joint work with Sushant Sachdeva.<br><br>See you Friday at 11am in the Stat&#39;s classroom.<br><br>Regards,<br>sekhar<br></div>