Balancing and Conditioning

There are two preprocessing steps one may perform on a matrix A in order to make its eigenproblem easier. The first is permutation, or reordering the rows and columns to make A more nearly upper triangular (closer to Schur form): A' = PAP^T, where P is a permutation matrix. If A' is permutable to upper triangular form (or close to it), then no floating-point operations (or very few) are needed to reduce it to Schur form. The second is scaling by a diagonal matrix D to make the rows and columns of A' more nearly equal in norm: A''= DA'D^-1. Scaling can make the matrix norm smaller with respect to the eigenvalues, and so possibly reduce the inaccuracy contributed by roundoff [106, Chap. II/11]. We refer to these two operations as balancing.

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

The output parameters of xGEEVX -- SCALE (real array of length N), ILO (integer), IHI (integer) and ABNRM (real) -- describe the result of balancing a matrix A into A'', where N is the dimension of A. The matrix A'' is block upper triangular, with at most three blocks: from 1 to ILO-1, from ILO to IHI, and from IHI+1 to N. The first and last blocks are upper triangular, and so already in Schur form. These are not scaled; only the block from ILO to IHI is scaled. Details of the scaling and permutation are described in SCALE (see the specification of xGEEVX or xGEBAL for details). The one-norm of A'' is returned in ABNRM.

The condition numbers described in earlier subsections are computed for the balanced matrix A'', and so some interpretation is needed to apply them to the eigenvalues and eigenvectors of the original matrix A. To use the bounds for eigenvalues in Tables 4.5 and 4.6, we must replace |E|₂ and |E|_F by $O(\epsilon) \Vert A''\Vert = O(\epsilon) \cdot {\tt ABNRM}$. To use the bounds for eigenvectors, we also need to take into account that bounds on rotations of eigenvectors are for the eigenvectors x'' of A'', which are related to the eigenvectors x of A by DPx=x'', or x=P^T D^-1x''. One coarse but simple way to do this is as follows: let $\theta''$ be the bound on rotations of x'' from Table 4.5 or Table 4.6 and let $\theta$ be the desired bound on rotation of x. Let

$$\kappa (D) = \frac{{\rule[-.25cm]{0cm}{.5cm} \max_{{\tt ILO}... ...}(i)}} {\min_{{\tt ILO} \leq i \leq {\tt IHI}} {\tt SCALE}(i)}$$

be the condition number of D. Then

$$\sin \theta \leq \kappa(D) \cdot \sin \theta'' \; \; .$$

The numerical example in subsection 4.8 does no scaling, just permutation.