[Applied Math Colloq.] Graph approximation and local clustering, with applications to the solution of diagonally-dominant systems of linear equations
Speaker: Daniel Spielman ,
Date: November 17 2008
Time: 4:30PM to 5:30PM
Location: Building 4, Room 231
Relevant URL:
Refreshments at 4:00 PM in Building 2, Room 349
(Applied Math Common Room)
ABSTRACT:
We discuss several fascinating concepts and algorithms in graph theory that arose in the design of a nearly-linear time algorithm for solving diagonally-dominant linear systems. We begin by defining a new notion of what it means to approximate a graph by another graph, and explain why these sparse approximations enable the fast solution of linear equations. To build these sparsifiers, we rely on low-stretch spanning trees, random matrix theory, spectral graph theory, and graph partitioning algorithms.
The need to quickly partition a graph leads us to the local clustering problem: given a vertex in a massive graph, output a small cluster near that vertex in time proportional to the size of the cluster.
We use all these tools to design nearly-linear time algorithms for solving diagonally-dominant systems of linear equations, and give some applications.
This talk focuses on joint work with Shang-Hua Teng, and touches on work by Vaidya, Gremban, Miller, Koutis, Emek, Elkin, Andersen, Chung, Lang, Daitch, Srivastava and Batson.
See other events that are part of
See other events happening in November 2008
