ARC Colloquium: Rasmus Kyng (Yale)

Event Details
Contact

Dani Denton

denton at cc dot gatech dot edu

Summaries

Summary Sentence: Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple (Klaus 1116 E at 11am)

Full Summary: No summary paragraph submitted.

Video of this talk is available at: https://smartech.gatech.edu/handle/1853/56087

Full collection of talk videos are available at: https://smartech.gatech.edu/handle/1853/46836

Algorithms & Randomness Center (ARC)

Rasmus Kyng - Yale

Monday, November 28, 2016

Klaus 1116 East - 11am

Title:  
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple

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.

Bio:
Rasmus Kyng is a PhD student in Computer Science at Yale University, advised by Dan Spielman. Before attending Yale, he received a BA in Computer Science from the University of Cambridge in 2011. His research interests include graph algorithms, applied and theoretical machine learning, and linear systems.

URL: http://www.cs.yale.edu/homes/rjkyng/

Seminar webpage

Fall 2016 ARC Seminar Schedule

 

Additional Information

In Campus Calendar
No
Groups

ARC, College of Computing, School of Computer Science

Invited Audience
Faculty/Staff, Public, Undergraduate students, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
Algorithm and Randomness Center, ARC
Status
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Aug 8, 2016 - 6:36am
  • Last Updated: Apr 13, 2017 - 5:15pm