Large 00128

Fast Solvers for SDD Systems and Their Application to Image Processing

Gary Miller

Recorded 13 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian Matrix, appears ubiquitously in mathematical physics.

Due to the recent discovery of very fast solvers for these equations, they are becoming increasingly popular in combinatorial optimization, computer vision, computer graphics and machine learning.

This talk will give an overview of our solver algorithms, including a sequential algorithm for solving Symmetric Diagonally Domiate (SDD) linear systems in O(m log n) expected time to constant precision. We will also discus parallel versions of the solver with near linear work.

The talk will be motivated by considering the classic problem of image denoising. More recent convex formulations of this problem will natural lead us into better algorithms for problems such as approximate multicommodity flow and a faster flow algorithm for graphs with good separator structure.

Topics in this talk represent joint work with Guy Blelloch, Hui Han Chin, Anupam Gupta, Jon Kelner, Yiannis Koutis, Aleksander Madry, Richard Peng and Kanat Tangwongsan.

Watched 6360 times.