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₁ (A, B) P₂, where P₁ and P₂ are permutation matrices. The second one is a scaling by two-sided diagonal transformation D₁ and D₂ to make the elements of A''= D₁ A' D₂ and B'' = D₁ B' D₂ 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₁) and scaling (D₁) and the right permutations (P₂) and scaling (D₂) 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 $\Vert(E, F)\Vert _F$ by $O(\epsilon)\Vert(A'',B'')\Vert _F = O(\epsilon)\sqrt{ {\tt ABNRM}^2 + {\tt BBNRM}^2 }$. 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₂ P^T₂ x and y'' = D^-1₁ P₁ y, or x = P₂ D₂ x'' and y = P^T₁ D₁ x'' respectively. Let $\theta''$ be the bound on the rotation of x'' from Table 4.7 and Table 4.8 and let $\theta$ be the desired bound on the rotation of x. Let

$$\kappa(D_2)=\frac{ \max_{ {\tt ILO} \leq i \leq {\tt IHI} } ... ... { \min_{ {\tt ILO} \leq i \leq {\tt IHI} } {\tt RSCALE}(i) }$$

be the condition number of the right scaling D₂ with respect to matrix inversion. Then

$$\sin \theta \leq \kappa(D_2) \sin\theta''.$$

Similarly, for the bound of the angles $\phi$ and $\phi''$ of the left eigenvectors y'' and y, we have

$$\sin \phi \leq \kappa(D_1) \sin \phi'',$$

where $\kappa(D_1)$ is the condition number of the left scaling D₁ with respect to inversion,

$$\kappa(D_1)=\frac{ \max_{ {\tt ILO} \leq i \leq {\tt IHI} } ... ... { \min_{ {\tt ILO} \leq i \leq {\tt IHI} } {\tt LSCALE}(i) }.$$

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