Notes and References

Theory and computation of spectral properties of singular matrix pencils have been intensively studied during the last two decades. Much motivation has come from systems and control theory, for example, computing the controllable subspace and uncontrollable modes (e.g., see [348,447,120] and references therein). The basic theory dates back to Kronecker in 1890 [276] and is well presented in Gantmacher [187]. The method described there for computing the KCF is numerically unstable. Several authors have more recently proposed algorithms that reduce a singular $A - \lambda B$ to generalized Schur-staircase form which are numerically stable. They compute the exact GUPTRI form (or something similar) of a pencil $A' - \lambda B'$ differing only slightly from the input pencil $A - \lambda B$.

Kublanovskaya introduced the first staircase algorithm for computing the Jordan structure of matrices in 1966 [278]. She used a normalized RQ factorization for rank determinations and null space separations. In 1970 Ruhe [371] introduced the use of the SVD in the staircase algorithm. The use of the SVD in an algorithm based on the chain relations was introduced by Golub and Wilkinson [199] and further analyzed and generalized in [250]. Kågström and Ruhe [253,252] developed the first library-quality software for the complete reduction to Jordan normal form (JNF), with the capability of returning after different steps in the reduction. Recently, Chaitin-Chatelin and Frayssé [77] developed a nonstaircase qualitative approach. Kågström and Wiberg [254] considered the problem of computing partial canonical information for large-scale eigenvalue problems. They combined the implicitly restarted Arnoldi method (IRAM) [419] for computing a partial Schur form with staircase algorithms for computing the Jordan-Schur and the Weierstrass-Schur forms of matrices and regular matrix pencils, respectively.

Van Dooren [446,451] gave a generalization of Kublanovskaya's staircase algorithm [278] to singular pencils using unitary equivalence transformations. In 1977 Kublanovskaya introduced the $AB$ algorithm for computing the right singular structure and the Jordan structure of the zero eigenvalue for a singular pencil (e.g., see [279,280]). Kågström [251] gave an RGSVD/RGQZD algorithm that provided a base for later work on software. Beelen and Van Dooren presented a faster but less reliable algorithm which requires $O(m^2n)$ operations for an $m \times n$ pencil. Error bounds for computed quantities like reducing subspaces and eigenvalues were given by Demmel and Kågström [119] and were also implemented in their software [121,122].

Recently, several papers were published that use geometry of matrix and matrix pencil spaces to understand Jordan and Kronecker structure problems and algorithms. Demmel and Edelman [116] used the staircase algorithm to calculate the dimension of matrices and pencils with a given canonical form. Elmroth and Kågström [160] made a comprehensive study of the set of $2 \times 3$ pencils, the smallest nontrivial rectangular case. Edelman and Ma presented a geometrical explanation of staircase algorithm failures [154]. Edelman, Elmroth, and Kågström [152,153] study versatility and stratifications. They discuss and complete the mathematical theory for orbits and bundles of matrices (Arnold [18]) and pencils (Pokrzywa [367], De Hoyos [106]) and propose that knowledge of the closure relations may be applied in the staircase algorithm [153].

StratiGraph is a recent Java-based tool for computation and presentation of graphs displaying closure hierarchies of Jordan and Kronecker structures [248,159]. Given the dimension of the problem and a canonical structure, the user can easily get information about nearby Jordan and Kronecker structures in the closure hierarchy. The stratification of orbits of pencils associated with problems in control theory has recently been studied by several authors, including Hinrichsen and O'Halloran [231], Boley [55], and Garcia-Planas [188]. For control applications, the pencils of interest typically have no row indices or no column indices, which can be seen as special cases of the general $A - \lambda B$ problem.