Center for Computing Research
Support Theory for Preconditioning
When using an iterative method to solve a linear system of equations, a good choice of preconditioner can have a dramatic impact on runtime and robustness. Instead of solving a system Ax=b, you solve a preconditioned system M-1Ax=M-1b, where M is the preconditioner. A good preconditioner must have a variety of properties. First, the preconditioned system should converge quickly. This generally means that M-1A has a small condition number. Second, it should be easy to solve systems of the form My=z. And obviously the construction of the preconditioner should be efficient in both time and space.
The generation of good preconditioners involves as much art as science. The best preconditioners tend to be application-specific, exploiting insight into the precise problem being solved. A number of general purpose preconditioner have been developed which often work well in practice. The most widely used of these are variants on incomplete factorizations and approximate inverses. Unfortunately, these general purpose approaches tend to be poorly understood theoretically (except perhaps on model problems), and they sometimes perform badly. New ways of thinking about preconditioning are urgently needed.
Support theory is a fairly recent methodology for bounding condition numbers of preconditioned systems. More specifically, it is a set of tools and techniques for bounding extremal eigenvalues. For some iterative methods (conjugate gradients in particular), the ratio of largest to smallest eigenvalues provides an upper bound on the number of iterations.
Support theory began with the remarkable work of Pravin Vaidya in the early nineties in which he proposed and analyzed maximum weight spanning tree preconditioners for Laplacian matrices. Vaidya chose not to publish his work, but to produce commercial software instead. His software has had a significant impact in the structural analysis community. Fortunately, John Gilbert and Gary Miller recognized the significance of Vaidya's ideas and kept them from being lost. Miller and two of his students (Keith Gremban and Steve Guattery) formalized and greatly extended the techniques that Vaidya had used. In the process, they devised a new multi-level preconditioner and also developed a new analysis of incomplete Cholesky preconditioning. Unfortunately, none of this work has yet appeared in a journal, and so the ideas and techniques are largely unknown.
Shortly after Gremban finished his thesis, Nhat Nguyen and I found an application of support theory ideas to provide a new analysis of modified incomplete Cholesky preconditioning. This work was eventually combined with the concurrent efforts of Sivan Toledo, John Gilbert and Marshall Bern to become the first paper below.
To this point, all of the techniques being used were limited to very limited classes of matrices. Specifically, most of the results were for symmetric, diagonally dominant M-matrices, with a few results extending to all symmetric diagonally dominant matrices. The limitations of applicability and the challenges of the combinatorics frustrated all of us, and led to the near demise of the field.
The next big advance was made by Erik Boman. He realized that all the support-graph methods were merely a special case of a much larger and richer algebraic structure. The algebraic generalization encompasses the much more significant class of all symmetric positive-definite matrices. This realization has reinvigorated the field, enabling a wide variety of new results. These observations grew into the second paper below which introduces this algebraic support theory, and provides an extensive set of tools for bounding condition numbers. The first application of this expanded theory is the third paper, which extends Vaidya's techniques to address all diagonally dominant matrices. This extension is mentioned in passing in Vaidya's original manuscript, but no details are given. We are also working on the application of these ideas to systems coming from the finite element solution of elliptic PDEs, and also to provide better dropping strategies for incomplete factorization preconditioners.
The past several years have witnessed continued a continual broadening and deepening of both theoretical developments and applications of support theory by a number of researchers. Although I include pointers to some of this work below, this page is not a comprehensive bibliography.
- Support-Graph Preconditioners, Marshall Bern, John R. Gilbert, Bruce Hendrickson, Nhat Nguyen and Sivan Toledo. SIAM J. Matrix Anal. Appl. 27(4):930-951 (2006).
- Support Theory for Preconditioning, Erik Boman and Bruce Hendrickson. SIAM J. Matrix Anal. & Appl. 25(3):694-717 (2003).
- Maximum-Weight-Basis Preconditioners, Erik Boman, Doron Chen, Bruce Hendrickson and Sivan Toledo. In Numerical Linear Algebra and Applications 11:695-721, 2004.
- Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners, Erik Boman, Bruce Hendrickson and Steve Vavasis. Submitted to SIAM J. Matrix Anal. and Appl.
- Optimal Embeddings and Eigenvalues in Support Theory Erik Boman, Stephen Guattery and Bruce Hendrickson. SIAM Journal on Matrix Analysis and Applications 22(2):596-605 (2007).
- Algebraic Tools for Analyzing Preconditioners, Bruce Hendrickson (with Erik Boman). Invited talk at Preconditioning'03.
Abstract, powerpoint version of overheads
Although Vaidya never published his work, his PhD student Anil Joshi wrote a dissertation that includes discussion, analysis and extensions to Vaidya's original techniques. Related work that may be of interest includes several papers by Steve Guattery and others by Sivan Toledo as well as Keith Gremban's thesis. Sivan and his student Doron Chen have an implementation of Vaidya's preconditioners as part of their TAUCS solver package. They have an interesting paper in ETNA describing their empirical experiments with Vaidya's methods. In addition, Dan Spielman and Shanghua Teng have done some very interesting algorithmic work that has significantly improved the theoretical performance of support theory preconditioners.
This brief synopsis is undoubtedly subject to personal bias and is certainly incomplete. Please send corrections or additions to me at firstname.lastname@example.org
Contact: Hendrickson, Bruce A., email@example.com