Algorithm Design using Spectral Graph Theory
Dec 14, 2011
ABSTRACT:
Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is fast solvers for symmetric diagonally dominant (SDD) linear systems, which occur ubiquitously in combinatorial optimization, computer vision, computer graphics and machine learning.
This talk will give an overview of some progress on the solver algorithm, including a sequential algorithm for solving SDD linear systems in O(m log n log(1/epsilon)) expected time and some work on its parallelization.
Also, I will talk about some recent work on using SDD linear system solvers for various optimization problems. Specifically an algorithm for total variation minimization based image denoising, as well as ongoing work on extending the electrical flow framework to multicommodity flows.
Topics in this talk represent joint work with Guy Blelloch, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Gary Miller and Kanat Tangwongsan.
Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is fast solvers for symmetric diagonally dominant (SDD) linear systems, which occur ubiquitously in combinatorial optimization, computer vision, computer graphics and machine learning.
This talk will give an overview of some progress on the solver algorithm, including a sequential algorithm for solving SDD linear systems in O(m log n log(1/epsilon)) expected time and some work on its parallelization.
Also, I will talk about some recent work on using SDD linear system solvers for various optimization problems. Specifically an algorithm for total variation minimization based image denoising, as well as ongoing work on extending the electrical flow framework to multicommodity flows.
Topics in this talk represent joint work with Guy Blelloch, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Gary Miller and Kanat Tangwongsan.