Combinatorial and algebraic tools for optimal multilevel algorithms

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. 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 algebraic multigrid amenable to a combinatorial approach that provides natural graph-theoretical goals and provably fast parallel algorithms for the design of the two-level scheme