The algorithm for computing the GUPTRI form is based on two reductions
(staircase forms) [121].
The first is the -staircase form that reveals
the right singular structure and the Jordan structure of
the zero eigenvalue of
.
The -algorithm uses a finite number of unitary equivalence
transformations, where in
step
,
dimension of the
column null space of
and
dimension of the intersecting column null space of
and
are determined.
Here,
and
, and
for
correspond to the deflated matrix pair obtained after
the equivalence transformation in step
.
The structure indices (
-indices) display the Kronecker structure as follows:
Nonzero entries after each deflation are marked with
a unique letter (x from first step, y from second step, etc.),
and they appear in bold or italic.
The superdiagonal blocks of have full column rank and
the diagonal blocks of
have full row rank.
The nonzero entries of the full rank blocks are marked in
bold font.
We use this notation in later examples as well.
The diagonal blocks (defining the ``stairs'') in
are of size
and show the following information:
In general, let and
be complex
matrices.
Then it can be shown that there exist unitary matrices
and
such that
the matrix pencil
is transformed to
the following so-called
RZ-staircase form [121,122]:
U^*(A - B)V =
[
] -
[
],
where the staircase block structure of and
reveals the
right singular structure and the Jordan structure of
the zero eigenvalue of
:
The subblocks in (8.37) and (8.38)
have the following properties:
Three cases can appear in the -staircase form depending on
and
:
We see that the example above corresponds to case 3 and
that
does not have a
th block column.
The second reduction is the (left-infinity)-staircase form
that reveals the left singular structure and the Jordan structure of
the infinite eigenvalue of
.
This dual staircase form is obtained by working from the southeast
corner of
and replacing column compressions by row compressions
in the
-algorithm.
The block indices
and
are dimensions of corresponding
row null spaces and define the
-indices.
Moreover,
and
are the
number of
and
blocks, respectively.
Both the -staircase and
-staircase reductions give us two types of
structure elements which must be separated to
obtain the GUPTRI form.
For example, the right singular structure and the Jordan
structure of the zero eigenvalue are separated by first applying the
-staircase reduction to
and insisting on the same
right minimal indices.
Then we obtain
and are left with a pencil,
say,
corresponding to the zero eigenvalue.
Finally,
is obtained by transforming
to
-staircase form.
We return to the example and show the separated
-staircase and
-staircase forms:
|
|
|
In summary, the GUPTRI algorithm for computing
(8.34) and (8.35) comprises
seven reduction steps.
The first three steps apply the -staircase reduction to
different blocks of
, giving the right singular structure
(
) and the zero Jordan structure (
)
in the top left corner of
and
.
Similarly, the next three steps apply the
-staircase reduction
to different blocks of the remaining pencil, giving the infinite Jordan
structure (
) and the left singular structure
(
) in the bottom right corner of
and
.
Then a square regular pencil is left in the middle of the
transformed pencil, which corresponds to the finite and nonzero
eigenvalues of
.
By applying the QZ algorithm to this pencil,
the upper triangular block
is obtained.