"Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations"
Daniel Spielman, Yale University
Thursday, September 8, 2011 at 4:00 P.M.
Room 368 (3rd Floor CIT)
We survey several fascinating concepts and algorithms in graph theory that arise in the design of fast algorithms for solving linear equations in the Laplacian matrices of graphs. We will begin by explaining why linear equations in these matrices are so interesting.
The problem of solving linear equations in these matrices motivates a new notion of what it means for one graph to approximate another. This leads to the problem of approximating graphs by sparse graphs. Our algorithms for solving Laplacian linear equations will exploit surprisingly strong approximations of graphs by sparse graphs, and even by trees.
We will survey the roles that spectral graph theory, random matrix theory, graph sparsification, low-stretch spanning trees and local clustering algorithms play in the design of fast algorithms for solving Laplacian linear equations.
This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Boman, Hendrickson, Miller, Koutis, Emek, Elkin, Andersen, Chung, Lang, Srivastava and Batson.
Host: Claire Mathieu