A Combinatorial Approach to Preconditioners for Iterative System Solvers

Gary Miller (glmiller@cs.cmu.edu)
Carnegie Mellon
Joint work with Keith Gremban

Download slides here (gzipped PostScript file).

In trying to solve a linear system, a number of methods are available. In this work , Gary was interested in finding preconditioners that would accelerate the convergence of the basic iterative method. Famous iterative methods can also be cast in this light, i.e., they correspond to the basic iterative method with a particular choice of a preconditioner - such as the diagonal entries of the matrix, or the lower triangular part of the matrix, and so on.

The preconditioners used traditionally have the same dimensions as the original matrix. Gary and Keith decided on a not so traditional preconditioner. They augment the original graph/matrix with a "support tree". Intuitively we would like to have a preconditioner B for which it is easy to solve equations of the form B y = z (hopefully even in parallel), and which connects vertices of the original graph that are far apart -- so as to help "mix" the data faster across the graph, since in some sense, the iterative method stops when the mixing is complete.
A preconditioner that helps with this mixing is more likely to reduce number of iterative steps.
From the point of view of being able to solve By = z in parallel, a balanced tree seems like a good candidate.

The condition number of a matrix, given by a ratio between the largest and smallest (non-zero) eigenvalue of the matrix, determines the convergence rate of the iterative method. A good preconditioner B is such that the condition number of B-1A is smaller than that of A.

They showed how to use graph embeddings to estimate the condition number of a matrix in terms of the support of a matrix by another. The support itself can be bounded by the product of the gain of A with respect to B, and the congestion and dilation of an embedding of A into B. A good preconditioner should strike a balance between being able to support the original graph A and being supported by the graph A. They obtain good preconditioners by using separators to help construct their support tree, in such a way that they can obtain good embeddings.