Let `A` and `B` be `n`-by-`n` matrices.
A scalar is called a **generalized eigenvalue** and a
non-zero column vector `x` the corresponding **right generalized eigenvector**
if .
A non-zero column vector `y` satisfying
(where the superscript `H` denotes conjugate-transpose)
is called
the **left generalized eigenvector**
corresponding to .
(For simplicity,
we will usually omit the word ``generalized'' when no confusion
is likely to arise.)
If `B` is singular, we can have the **infinite eigenvalue**
, by which we mean
`Bx` = 0.
Note that if `A` is non-singular, then the equivalent problem
is perfectly well-behaved, and the infinite eigenvalue
corresponds to .
To deal with infinite eigenvalues,
the LAPACK routines return two values,
and ,
for each eigenvalue .
The first basic task of these routines is to compute the
all `n` pairs and `x` and/or `y` for a given
pair of matrices `A,B`.

If the determinant of is zero for all values of ,
the eigenvalue problem is called **singular**, and is signaled by some
(in the presence of roundoff, and may
be very small). In this case the eigenvalue problem is very ill-conditioned,
and in fact some of the other nonzero values of and may be
indeterminate [43][21][80][71].

The other basic task is to compute the
**generalized Schur decomposition** of the pair `A,B`.
If `A` and `B` are complex,
then the pair's generalized Schur decomposition is
, where `Q` and `Z` are unitary and
`S` and `P` are upper triangular.
The LAPACK routines normalize `P` to have
non-negative diagonal entries. Note that in this form,
the eigenvalues can be easily computed from the diagonals:
,
and so the LAPACK routines return
and . The generalized Schur
form depends on the order on which the eigenvalues appear on the
diagonal. In a future version of LAPACK, we will supply routines
to allow the user to choose this order.

If `A` and `B` are real,
then the pair's generalized Schur decomposition is
, ,
where `Q` and `Z` are orthogonal,
`P` is upper triangular,
and `S` is quasi-upper triangular
with 1-by-1 and 2-by-2 blocks on the diagonal.
The 1-by-1 blocks correspond to real generalized eigenvalues,
while the 2-by-2 blocks correspond to complex conjugate
pairs of generalized eigenvalues.
In this case, `P` is normalized so that diagonal
entries of `P`
corresponding to 1-by-1 blocks of `S` are non-negative,
while the (upper triangular) diagonal blocks of `P` corresponding
to 2-by-2 blocks of `S` are made diagonal.
Note that for real eigenvalues,
as for all eigenvalues in the complex case,
the and values corresponding to real eigenvalues
may be easily computed from the diagonal of `S` and `P`.
The and values corresponding to complex
eigenvalues are computed by computing ,
then computing the values that would result if
the 2-by-2 diagonal block of `S,P` were upper triangularized using
unitary transformations ,
and finally multiplying to get
and .

The columns of `Q` and `Z` are called **generalized Schur vectors**
and span pairs of **deflating subspaces** of `A` and `B` [72].
Deflating subspaces are a generalization of invariant subspaces:
The first `k` columns of `Z` span a right deflating subspace
mapped by both `A` and `B` into a left deflating subspace spanned by
the first `k` columns of `Q`. This pair of deflating subspaces corresponds
to the first `k` eigenvalues appearing at the top of `S` and `p`.

The computations proceed in the following stages:

- The pair
`A,B`is reduced to**generalized upper Hessenberg form**. If`A`and`B`are real this decomposition is , where`H`is upper Hessenberg (zero below the first subdiagonal),`T`is upper triangular and`U`and`V`are orthogonal. If`A`and`B`are complex, the decomposition is , with`U`and`V`unitary and`H`and`T`as before. This decomposition is performed by the subroutine xGGHRD, which computes`H`and`T`and optionally`U`and/or`V`. Note that in contrast to xGEHRD (for the standard nonsymmetric eigenvalue problem), xGGHRD does not compute U and V in a factored form. - The pair
`H,T`is reduced to generalized Schur form , (for`H`and`T`real) or , (for`H`and`T`complex) by subroutine xHGEQZ. The values and are also computed. The matrices`Z`and`Q`are optionally computed. - The left and/or right eigenvectors of the pair
`A`are computed by xTGEVC. One may optionally transform the right eigenvectors of`S,P`to the right eigenvectors of`A,B`(or of`H,T`) by passing`UQ,VZ`(or`Q,Z`) to xTGEVC.

In addition, the routines xGGBAL and xGGBAK
may be used to **balance** the
pair `A,B` prior to reduction to generalized Hessenberg form.
Balancing involves
premultiplying `A` and `B` by one permutation
and postmultiplying them by another,
to try to make `A,B` as nearly triangular
as possible,
and then ``scaling'' the matrices by
premultiplying `A` and `B` by one diagonal
matrix and postmultiplying by another in order to
make the rows and columns of `A` and `B`
as close in norm to 1 as possible.
These transformations can improve speed and
accuracy of later processing in some cases;
however, the scaling step can sometimes make
things worse.
Moreover,
the scaling step will significantly change the generalized
Schur form that results.
xGGBAL performs the balancing,
and xGGBAK back transforms the eigenvectors of the balanced matrix pair.

-------------------------------------------------------------------------- Type of matrix Single precision Double precision and storage scheme Operation real complex real complex -------------------------------------------------------------------------- general Hessenberg reduction SGGHRD CGGHRD DGGHRD ZGGHRD balancing SGGBAL CGGBAL DGGBAL ZGGBAL back transforming SGGBAK CGGBAK DGGBAK ZGGBAK -------------------------------------------------------------------------- Hessenberg Schur factorization SHGEQZ CHGEQZ DHGEQZ ZHGEQZ -------------------------------------------------------------------------- (quasi)triangular eigenvectors STGEVC CTGEVC DTGEVC ZTGEVC --------------------------------------------------------------------------

A future release of LAPACK will include the routines xTGEXC, xTGSYL, xTGSNA and xTGSEN, which are analogous to the routines xTREXC, xTRSYL, xTRSNA and xTRSEN. They will reorder eigenvalues in generalized Schur form, solve the generalized Sylvester equation, compute condition numbers of generalized eigenvalues and eigenvectors, and compute condition numbers of average eigenvalues and deflating subspaces.

Tue Nov 29 14:03:33 EST 1994