Solving large optimization problems using spectral graph theory

Spectral Graph Theory is the interplay between linear algebra and combinatorial graph theory. One application of this interplay is a nearly linear time solver for Symmetric Diagonally Dominate systems (SDD). This seemingly restrictive class of systems has received much interest in the last 15 years. Both algorithm design theory and practical implementations have made substantial progress. There is also a growing number of problems that can be efficiently solved using SDD solvers including: image segmentation, image denoising, finding solutions to elliptic equations, computing maximum flow in a graph, graph sparsification, and graphics. All these examples can be viewed as special case of convex optimization problems.

Authors

• Gary L. Miller

Keywords

• linear systems
• graph theory
• optimization