One difference at least in theory between the standard eigenvalue problem and the generalized eigenvalue problem discussed in the previous sections is the appearance of infinite eigenvalues whenever is singular. The standard method for solving dense generalized eigenvalue problems is the QZ algorithm; see §8.2. However, there is more to the story. For example, if and have a common null space, then the generalized eigenvalue problem is ill posed in the sense that arbitrary small perturbations may change the eigenvalues completely. In general, the QZ algorithm is not capable of handling this type of problem in a reliable way. It is necessary to apply a regularization technique by allowing a deflation criterion for range or null space separations in finite precision and thereby make it possible to compute the eigenvalues of a nearby problem. Typically, the distance from the regularized nearby problem to the original problem is proportional to the size of the deflation tolerance used.
In this section we
give an introduction to the theory, algorithms,
and software for solving the most general
form of the
including the case when and are rectangular matrices.
The software computes a generalization of
the Schur canonical form to matrix pairs
called GUPTRI (generalized upper triangular) form
P^ (A - B) Q =
ccc A_r - B_r & * & *
0 & A_reg - B_reg & *
0 & 0 & A_l - B_l , with the following properties: it separates the regular and singular parts of the problem. is the regular part and it includes all eigenvalues. The blocks and in (8.28) correspond to the singular part and have a special block structure. Here denotes arbitrary conforming submatrices.
Before we make a complete description of the GUPTRI form and present algorithms and software for computing it, we need to introduce some new notation and definitions associated with singular problems. Some of the material presented is by definition rather technical and comprehensive. In our effort to simplify the presentation we also provide several examples that illustrate the nature of singular and nearly singular eigenproblems, the difficulties encountered in dealing with them, and how they can be overcome.