Singular Matrix Pencils
  B. Kågström

One difference at least in theory between the standard eigenvalue problem $Ax = \lambda x$ and the generalized eigenvalue problem $Ax = \lambda Bx$ discussed in the previous sections is the appearance of infinite eigenvalues whenever $B$ 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 $A$ and $B$ 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 $Ax = \lambda Bx$ problem, including the case when $A$ and $B$ are rectangular matrices. The software computes a generalization of the Schur canonical form to matrix pairs $\{A,B\}$ 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. $A_{reg} - \lambda B_{reg}$ is the regular part and it includes all eigenvalues. The blocks $A_r - \lambda B_r$ and $A_l - \lambda B_l$ 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.