next up previous contents index
Next: Deflating Subspaces and Condition Up: Generalized Nonsymmetric Eigenproblems Previous: Eigenvalues, Eigenvectors and Generalized   Contents   Index

Balancing

The routine xGGBAL may be used to balance the matrix pair (A,B) prior to reduction to generalized Hessenberg form. Balancing involves two steps, either of which is optional:

1.
First, xGGBAL attempts to permute (A,B) by an equivalence transformation to block upper triangular form:

\begin{displaymath}P_1(A,B)P_2 = (A^\prime,B^\prime) = \left(
\left[
\begin{ar...
... \\
0 & 0 & B^\prime_{33} \\
\end{array} \right]
\right)
\end{displaymath}

where P1 and P2 are permutation matrices and $A^\prime_{11}$, $A^\prime_{33}$, $B^\prime_{11}$ and $B^\prime_{33}$ are upper triangular. Thus the matrix pair is already in generalized Schur form outside the central diagonal blocks $A^\prime_{22}$ and $B^\prime_{22}$ in rows and columns ILO to IHI. Subsequent operations by xGGBAL, xGGHRD or xHGEQZ need only be applied to these rows and columns; therefore ILO and IHI are passed as arguments to xGGHRD and xHGEQZ. This can save a significant amount of work if ILO > 1 or IHI < n. If no suitable permutations can be found (as is very often the case), xGGBAL sets ILO = 1 and IHI = n, and $A^\prime_{22}$ is the whole of A and $B^\prime_{22}$ is the whole of B.

2.
Secondly, xGGBAL applies diagonal equivalence transformations to $(A^\prime,B^\prime)$ to attempt to make the matrix norm smaller with respect to the eigenvalues and tries to reduce the inaccuracy contributed by roundoff [100]:

\begin{eqnarray*}
(A^{\prime\prime},B^{\prime\prime}) & = &
D_1(A^\prime,B^\pr...
...& 0 & 0 \\
0 & D'_2 & 0 \\
0 & 0 & I \\ \end{array} \right]
\end{eqnarray*}


This can improve the accuracy of later processing in some cases; see subsection 4.11.1.2.

If the matrix pair (A,B) was balanced by xGGBAL, then eigenvectors computed by subsequent operations are eigenvectors of the balanced matrix pair $(A^{\prime\prime},B^{\prime\prime})$. xGGBAK must then be called to transform them back to eigenvectors of the original matrix pair (A,B). Note that these transformations can improve speed and accuracy of later processing in some cases; however, the diagonal transformation step can occasionally make the norm of the pencil $(A^\prime,B^\prime)$ larger and hence degrade the accuracy.


next up previous contents index
Next: Deflating Subspaces and Condition Up: Generalized Nonsymmetric Eigenproblems Previous: Eigenvalues, Eigenvectors and Generalized   Contents   Index
Susan Blackford
1999-10-01