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
problem,
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
[121,122]:
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.