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:
, 
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.
, 
(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.
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
--------------------------------------------------------------------------
Table 2.15: Computational routines for the generalized nonsymmetric eigenproblem
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.