... defined2.1
If we tried to compute the trivial eigenvalues in the same way as the nontrivial ones, that is by taking ratios of the leading n-r diagonal entries of XT AT AX and XT BT B X, we would get 0/0. For a detailed mathematical discussion of this decomposition, see the discussion of the Kronecker Canonical Form in [53].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... xTGSJA2.2
If m-k-l < 0, we may add some zero rows to A23 to make it upper triangular.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... digit4.1
This is the case on Cybers, Cray X-MP, Cray Y-MP, Cray 2 and Cray C90.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... xLAMCH4.2
See subsection 2.2.3 for explanation of the naming convention used for LAPACK routines.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... PCs4.3
Important machines that do not implement the IEEE standard include the Cray XMP, Cray YMP, Cray 2, Cray C90, IBM 370 and DEC Vax. Some architectures have two (or more) modes, one that implements IEEE arithmetic, and another that is less accurate but faster.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... xSTEVR.4.4
xSYEVR and the other drivers call ILAENV to check if IEEE arithmetic is available, and uses another algorithm if it is not. If LAPACK is installed by following the directions in Chapter 6, then ILAENV will return the correct information about the availability of IEEE arithmetic. If xSYEVR or the other drivers are used without this installation procedure, then the default is for ILAENV to say the IEEE arithmetic is available, since this is most common and faster.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
....4.5
Sometimes our algorithms satisfy only ${\rm alg}(z)=f(z+ \delta) + \eta$ where both $\delta$ and $\eta$ are small. This does not significantly change the following analysis.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... small4.6
More generally, we only need Lipschitz continuity of f, and may use the Lipschitz constant in place of f' in deriving error bounds.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... exist)4.7
This is a different use of the term ill-posed than used in other contexts. For example, to be well-posed (not ill-posed) in the sense of Hadamard, it is sufficient for f to be continuous, whereas we require Lipschitz continuity.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... described4.8
There are some caveats to this statement. When computing the inverse of a matrix, the backward error E is small taking the columns of the computed inverse one at a time, with a different E for each column [47]. The same is true when computing the eigenvectors of a nonsymmetric matrix. When computing the eigenvalues and eigenvectors of $A - \lambda B$, $AB- \lambda I$ or $BA- \lambda I$, with A symmetric and B symmetric and positive definite (using xSYGV or xHEGV) then the method may not be backward normwise stable if B has a large condition number $\kappa_{\infty}(B)$, although it has useful error bounds in this case too (see section 4.10). Solving the Sylvester equation AX+XB=C for the matrix X may not be backward stable, although there are again useful error bounds for X [66].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... error4.9
For other algorithms, the answers (and computed error bounds) are as accurate as though the algorithms were componentwise relatively backward stable, even though they are not. These algorithms are called componentwise relatively forward stable.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bound4.10
As discussed in section 4.2, this approximate error bound may underestimate the true error by a factor p(n) which is a modestly growing function of the problem dimension n. Often $p(n) \leq 10n$.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... suppose4.11
This and other numerical examples were computed in IEEE single precision arithmetic [4] on a DEC 5000/120 workstation.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bound4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bounds4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... ill-conditioned4.3
These bounds are special cases of those in section 4.8.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bounds4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... eigenvalue.4.1
Although such a one-to-one correspondence between computed and true eigenvalues exists, it is not as simple to describe as in the symmetric case. In the symmetric case the eigenvalues are real and simply sorting provides the one-to-one correspondence, so that $\hat{\lambda}_1 \leq \cdots \leq \hat{\lambda}_n$ and $\lambda_1 \leq \cdots \leq \lambda_n$. With nonsymmetric matrices $\hat{\lambda}_i$ is usually just the computed eigenvalue closest to $\lambda_i$, but in very ill-conditioned problems this is not always true. In the most general case, the one-to-one correspondence may be described in the following nonconstructive way: Let $\lambda_i$ be the eigenvalues of A and $\hat{\lambda}_i$ be the eigenvalues of A+E. Let $\lambda_i(t)$ be the eigenvalues of A+tE, where t is a parameter, which is initially zero, so that we may set $\lambda_i (0) = \lambda_i$. As t increase from 0 to 1, $\lambda_i(t)$ traces out a curve from $\lambda_i$ to $\hat{\lambda}_i$, providing the correspondence. Care must be taken when the curves intersect, and the correspondence may not be unique.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bounds4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... $\{\hat{v}_i \, , \, i \in {\cal I}\}$4.1
These bounds are special cases of those in sections 4.7 and 4.8, since the singular values and vectors of A are simply related to the eigenvalues and eigenvectors of the Hermitian matrix $\left( \begin{array}{cc} 0 & A^H \\ A & 0 \end{array} \right) $ [55, p. 427].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bounds4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... magnitude4.1
This bound is guaranteed only if the Level 3 BLAS are implemented in a conventional way, not in a fast way as described in section 4.13.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... large4.2
Another interpretation of chordal distance is as half the usual Euclidean distance between the projections of $\hat{\lambda}_i$ and $\lambda_i$ on the Riemann sphere, i.e., half the length of the chord connecting the projections.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bounds4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... suppose4.1
This numerical example is computed in IEEE single precision arithmetic on a SUN Sparcstation 10 workstation.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... pair.4.2
As for the nonsymmetric eigenvalue problem there is an one-to-one correspondence between computed and exact eigenvalue pairs, but the correspondence is not as simple to describe as in the generalized symmetric definite case. (Since the eigenvalues are real, sorting provides the one-to-one correspondence). For well-conditioned generalized eigenvalues $({\hat{\alpha}}_i, {\hat{\beta}}_i)$ is usually the closest eigenvalue pair to $({\alpha}_i, {\beta}_i)$ in the chordal metric, but in ill-conditioned cases this is not always true. The (nonconstructive) correspondence between computed and exact eigenvalues described in footnote 1 for the standard nonsymmetric eigenvalue problem is also applicable here.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... eigenvalues4.3
In order to make the definition $( {\alpha}_{\cal I}, {\beta}_{\cal I} )$ of the cluster average in chordal sense meaningful for all cases that can appear we have to make a normalization of the matrix pair in generalized Schur form. First, we make each nonzero bii nonnegative real by premultiplying by the appropriate complex number with unit absolute value. Secondly, if all bii in the cluster are zero, then we make all real parts of each nonzero aii nonnegative real. This means that if there is at least one finite eigenvalue in the cluster (i.e., at least one bii is nonzero in B11), then ${\rm trace}(B_{11}) = \sum_{i \in {\cal I}} {\beta}_i$ is nonzero and the cluster average is finite. If all bii are zero and some aii is nonzero then ${\rm trace}(A_{11}) = \sum_{i \in {\cal I}} {\alpha}_i$ is nonzero and the cluster average is infinity. Note the pencil is singular if one pair (aii, bii) = (0,0) or close to singular if both aii and bii are tiny (see Section 4.11.1.4).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... bound4.10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... example4.11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... output)5.1
(Input or output) means that the argument may be either an input argument or an output argument, depending on the values of other arguments; for example, in the xyySVX driver routines, some arguments are used either as output arguments to return details of a factorization, or as input arguments to supply details of a previously computed factorization.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... (workspace/output)5.2
(Workspace/output) means that the argument is used principally as a work array, but may also return some useful information (in its first element)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... DREAL.6.1
Changing DBLE to DREAL must be selective, because instances of DBLE with an integer argument must not be changed. The compiler should flag any instances of DBLE with a COMPLEX*16 argument if it does not accept them.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... matrix.7.1
The requirement is stated ``LDA $\geq$ max(1,N)'' rather than simply ``LDA $\geq$ N'' because LDA must always be at least 1, even if N = 0, to satisfy the requirements of standard Fortran; on some systems, a zero or negative value of LDA would cause a run-time fault.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Susan Blackford
1999-10-01