|
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 new 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. To learn more
about support theory research, click here.
|
