Support Theory for Preconditioning

A new theorem for bounding support numbers (generalized eigenvalues) where the matrices have a known factorization (not necessarily square or triangular) is presented, which generalizes earlier results based on graph theory.

Abstract

We present support theory, a set of techniques for bounding extreme eigenvalues and condition numbers for matrix pencils. Our intended application of support theory is to enable proving condition number bounds for preconditioners for symmetric, positive definite systems. One key feature sets our approach apart from most other works: We use support numbers instead of generalized eigenvalues. Although closely related, we believe support numbers are more convenient to work with algebraically. This paper provides the theoretical foundation of support theory and describes a set of analytical tools and techniques. For example, we present a new theorem for bounding support numbers (generalized eigenvalues) where the matrices have a known factorization (not necessarily square or triangular). This result generalizes earlier results based on graph theory. We demonstrate the utility of this approach by a simple example: block Jacobi preconditioning on a model problem. Also, our analysis of a new class of preconditioners, maximum-weight basis preconditioners, in [E. G. Boman, D. Chen, B. Hendrickson, and S. Toledo, Numer. Linear Algebra Appl., to appear] is based on results contained in this paper.