May 3, 2007
Ioannis Koutis
3:30 PM, 3305 Newell-Simon Hall
Thesis Oral
Title: Combinatorial and Algebraic Tools for Optimal Multilevel Algorithms
Abstract:
This dissertation presents combinatorial and algebraic tools that enable the design of the first linear work parallel iterative algorithm for solving linear systems involving Laplacian matrices of planar graphs. The major departure of this work from prior suboptimal and inherently sequential approaches is centered around: (i)the partitioning of planar graphs into fixed size pieces that share small boundaries, by means of a local “bottom-up” approach that improves the customary “top-down” approach of recursive bisection, (ii) the replacement of monolithic global preconditioners by graph approximations that are built as aggregates of miniature preconditioners.
In addition, we present extensions to the theory and analysis of Steiner tree preconditioners and we construct more general Steiner graphs that lead to natural linear time solvers for classes of graphs that are known a priori to have certain structural properties. We also present a graph-theoretic approach to classical algebraic multigrid algorithms. We show that their design can be recast as the construction of Steiner graph preconditioners. This observation makes the analysis of multigrid amenable to support theory tools and leads to the design of linear work parallel algorithms that can be as fast as currently used heuristics, but also provide strict guarantees.
Thesis Committee:
Gary Miller, Chair
Alan Frieze
John Lafferty
Daniel Spielman, Yale University
