Support Theory Research

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 Bruce Hendrickson 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 following paper.

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 following paper 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 following 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.

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 describing their empirical experiments with Vaidya's methods.

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.

Dan Spielman and Shang-Hua Teng wrote two papers describing preconditioners for symmetric diagonally-dominant linear systems. The first paper shows how to solve such linear systems in time O(m^1.31). In the second paper they improve this result and show how to solve such linear systems in nearly-linear time.

Recently, Erik Boman, Bruce Hendrickson and Stephen Vavasis wrote a paper which shows how support preconditioners can be applied to a class of linear systems arising from use of the finite element method to solve linear elliptic problems.

For a list of support theory publications, click here.