[YPNG] YPNG, Friday 21 July 2017

[Sekhar Tatikonda]

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
for
Laplacian matrices. We present a simple, nearly linear time algorithm that
approximates
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
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.

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

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