Approximate Gaussian Elimination for Laplacians

Speaker: Rasmus Kyng , Yale

Date: Wednesday, September 28, 2016

Time: 3:00 PM to 4:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Pritish Kamath and Akshay Degwekar, MIT CSAIL

Contact: Rebecca Yadegar,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: Rasmus Kyng: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar Series 2016/2017.

Created by Rebecca Yadegar Email at Wednesday, September 21, 2016 at 2:35 PM.