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 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
operations for an
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 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
problem.