Speaker: Assistant Professor Rasmus Kyng, ETH Zurich
Date and Time: September 29, 2:00-3:00 p.m.
Location: Coda, Room 114
Host: School of CSE Professor Edmond Chow

Title: Robust and Practical Solution of Laplacian Equations by Approximate Elimination

Abstract: In this talk, I will describe a new algorithm for solving Laplacian (and SDDM) linear equations. We introduce a variant of the approximate Cholesky factorization of Kyng and Sachdeva (FOCS 2016), and we experimentally demonstrate that this method performs well in practice across a broad range of problem classes. Our experiments suggest that our solver is much more robust than existing solvers for Laplacian linear equations, while retaining good performance across all instances.

Our factorization approach is simple: we eliminate matrix rows/columns one at a time and use sampling to update the remaining entries of the matrix, approximating complete Cholesky factorization. Unlike earlier approaches, our sampled entries always maintain a connected support graph on the neighbors of the eliminated variable.

This talk is based on joint work with Yuan Gao and Daniel Spielman.

Preprint: https://arxiv.org/abs/2303.00709

Bio: Rasmus Kyng is an assistant professor of theoretical computer science at ETH Zurich. Before joining the ETH CS department in 2019, he was a postdoctoral fellow at Harvard SEAS and the Simons Institute at UC Berkeley. In 2017, he received a PhD in computer science from Yale University, where he was advised by Daniel Spielman.

His work focuses on fast algorithms for solving graph problems, convex optimization, and structured linear equations. In addition, he develops hardness results for basic algorithmic problems and probability theoretic tools for algorithmic applications. His research has won the FOCS'22 best paper and FOCS'17 best student paper awards, and the ICBS 2023 Frontiers of Science Award for Best Paper in Theoretical Computer Science 2018-2022.