The Laplacian Matrices of Graphs: Algorithms and Applications

Undergraduate Seminar
Event time: 
Thursday, April 19, 2018 - 6:00pm
LOM 215
Dan Spielman
Speaker affiliation: 
Yale University
Event description: 

The Laplacian matrices of graphs arise in many fields, including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they appear in so many applications.

We then survey recent ideas that allow us to solve systems of linear equations in Laplacian matrices in nearly linear time, emphasizing the utility of graph sparsification—the approximation of a graph by a sparser one—and a recent algorithm of Kyng and Sachdeva that uses random sampling to accelerate Gaussian Elimination.