** Next:** Computing s_{i}, , and
** Up:** Further Details: Error Bounds
** Previous:** Overview
** Contents**
** Index**

###

Balancing and Conditioning

As in the standard nonsymmetric eigenvalue problem (section 4.8.1.2),
two preprocessing steps
may be performed on the input matrix pair **(***A*, *B*).
The first one is a **permutation**, reordering the rows and columns
to attempt to make *A* and *B* block upper triangular, and
therefore to reduce the order of the eigenvalue problems to be solved:
we let
**(***A*',*B*') = *P*_{1} (*A*, *B*) *P*_{2}, where *P*_{1} and *P*_{2} are
permutation matrices.
The second one is a **scaling**
by two-sided diagonal transformation *D*_{1}
and *D*_{2} to make the elements of
*A*''= *D*_{1} *A*' *D*_{2} and
*B*'' = *D*_{1} *B*' *D*_{2}
have magnitudes as close to unity as possible, so as to reduce the effect
of the roundoff error made by the later algorithm [100].
We refer to these two operations as *balancing*.

Balancing is performed by driver xGGEVX, which calls computational
routine xGGBAL. The user may choose to optionally
permute, scale, do both or do either;
this is specified by the input parameter
`BALANC` when xGGEVX is called.
Permuting has no effect on the condition numbers
or their interpretation as described in the previous subsections. Scaling does,
however, change their interpretation, as we now describe.

The output parameters of xGGEVX -
`ILO`(integer), `IHI`(integer),
`LSCALE`(real array of length N),
`RSCALE`(real array of length N),
`ABNRM`(real) and
`BBNRM`(real) -
describe the result of balancing the matrix pair **(***A*, *B*) to
**(***A*'',*B*''), where N is the dimension of **(***A*,*B*).
The matrix pair **(***A*'',*B*'') has block upper triangular
structure, with at most three blocks: from 1 to `ILO`-1,
from `ILO` to `IHI`, and from `IHI`+1 to N (see section
2.4.8). The first and last blocks are upper
triangular, and so already in generalized Schur form. These blocks are not
scaled; only the block from `ILO` to `IHI` is scaled.
Details of the left permutations (*P*_{1}) and scaling (*D*_{1})
and the right permutations (*P*_{2}) and scaling (*D*_{2})
are described in `LSCALE` and `RSCALE`, respectively.
(See the specification of xGGEVX or xGGBAL for more information).
The one-norms of *A*'' and *B*'' are returned in
`ABNRM` and `BBNRM`, respectively.

The condition numbers
described in earlier subsections are computed
for the balanced matrix pair **(***A*'',*B*'') in xGGEVX, and so
some interpretation is needed to apply them to the eigenvalues
and eigenvectors of the original matrix pair **(***A*, *B*).
To use the bounds for eigenvalues in Tables 4.7 and 4.8,
we must replace
by
.
To use the bounds for eigenvectors, we also need to take
into account that bounds on rotation of the right and left eigenvectors
are for the right and left eigenvectors *x*'' and *y*'' of
*A*'' and *B*'', respectively, which are related to
the right and left eigenvectors *x* and *y* by
*x*'' = *D*^{-1}_{2} *P*^{T}_{2} *x* and
*y*'' = *D*^{-1}_{1} *P*_{1} *y*,
or
*x* = *P*_{2} *D*_{2} *x*'' and
*y* = *P*^{T}_{1} *D*_{1} *x*'' respectively.
Let
be the bound on the rotation of *x*''
from Table 4.7 and Table 4.8 and
let
be the desired bound on the rotation of *x*. Let

be the condition number of the right scaling *D*_{2} with respect
to matrix inversion. Then

Similarly, for the bound of the angles
and
of the
left eigenvectors *y*'' and *y*, we have

where
is the condition number of the left
scaling *D*_{1} with respect to inversion,

The numerical example in section 4.11
does no scaling, just permutation.

** Next:** Computing s_{i}, , and
** Up:** Further Details: Error Bounds
** Previous:** Overview
** Contents**
** Index**
*Susan Blackford*

*1999-10-01*