[YPNG] YPNG, Friday 21 July 2017
sekhar.tatikonda at yale.edu
Tue Jul 18 07:39:21 EDT 2017
This Friday in the YPNG seminar Rasmus Kyng will talk about:
Title: Approximate Gaussian Elimination for Laplacians
Abstract: We show how to perform sparse approximate Gaussian elimination
Laplacian matrices. We present a simple, nearly linear time algorithm that
a Laplacian by a matrix with a sparse Cholesky factorization – the version
elimination for positive semi-definite matrices. We compute this
subsampling standard Gaussian elimination. This is the first nearly linear
for Laplacian systems that is based purely on random sampling, and does not
any graph theoretic constructions such as low-stretch trees, sparsifiers,
The crux of our proof is the use of matrix martingales to analyze the
Joint work with Sushant Sachdeva.
See you Friday at 11am in the Stat's classroom.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the YPNG