Spectral graph sparsification Part 1: – (The Combinatorial Multigrid Solver)

We discuss the latest developments on linear system solvers for very large sparse Symmetric Diagonally Dominate system (SDD). This seemingly restrictive class of systems has received substantial interest and in the last 20 years both algorithm design theory and practical implementations have made substantial progress. Due to the nearly linear run times for these systems 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, and other problems in graphics and data mining.

In this first talk we present the design of a “Combinatorial Multigrid” (CMG) solver. The CMG solver borrows notions from a widely studied class of solvers collectively known as Multigrid, but it is the first of the kind that provides provable “black-box” guarantees for general sparse SDD systems.

The key to the CMG properties is combinatorial preconitioning, a set of techniques that uses spectral graph theory for the construction of matrix and graph sparsifiers that roughly preserve the spectral profile of the given matrix. We review basic notions of combinatorial preconditioning and in particular discuss how multiway graph partitioning to tightly-connected, relatively isolated isolated clusters is the sufficient and necessary property for the fast convergence of multigrid.

Joint work with Gary Miller and Richard Peng