skip to main content

TCS+ Talk

Wednesday, September 14, 2016
10:00am to 11:00am
Add to Cal
Annenberg 308
Fast Approximate Gaussian Elimination for Laplacians
Sushant Sachdeva, Google,

Available remotely at Google Hangouts:


Abstract: Solving systems of linear equations in graph Laplacians is a fundamental primitive in scientific computing. Starting with the seminal work of Spielman-Teng that gave the first nearly-linear time algorithm for solving Laplacian systems, there has been a long line of work giving faster Laplacian solvers. These solvers have had a large impact on the design of fast graph algorithms. In this talk, I'll present a very simple, nearly-linear time Laplacian solver that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. Our solver builds a sparse Cholesky factorization for Laplacians — the symmetric version of Gaussian elimination. More precisely, it approximates a Laplacian L as U'U, where U is a sparse upper triangular matrix. Since triangular matrices are easy to invert, this immediately implies a fast Laplacian solver via iterative refinement. The analysis is based on concentration of matrix martingales.
This is joint work with Rasmus Kyng, and will appear at the upcoming FOCS.
About the Speaker: Sushant Sachdeva is a research scientist at Google. He is interested in Algorithms, and its connections to optimization, machine learning, and statistics. His recent research focus has been the design of fast algorithms for graph problems. He completed his postdoc at Yale with Dan Spielman (2016), his PhD from Princeton (2013) under Sanjeev Arora, and his BTech from IIT Bombay (2008). He is the recipient of Simons Berkeley Research Fellowship (2013), and the IITB President of India Gold Medal (2008).


For more information, please contact Thomas Vidick by email at [email protected].