[YPNG] YPNG, Friday 21 July 2017

Sekhar Tatikonda sekhar.tatikonda at yale.edu
Tue Jul 18 07:39:21 EDT 2017

Hi Everyone,

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
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 Laplacian systems that is based purely on random sampling, and does not
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
Joint work with Sushant Sachdeva.

See you Friday at 11am in the Stat's classroom.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/ypng/attachments/20170718/2f1f8ae6/attachment.html 

More information about the YPNG mailing list