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 became 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.
Other related work includes a theoretical paper by John Reif (and its errata), and extensions to complex arithmetic of Gremban's multilevel preconditioner by Vicki Howle and Steve Vavasis.
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
Return to Bruce's home page