** Next:** Balancing
** Up:** Generalized Nonsymmetric Eigenproblems
** Previous:** Generalized Nonsymmetric Eigenproblems
** Contents**
** Index**

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**
of the pair **(***A*,*B*),
if
.
A non-zero column vector *y* satisfying
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-defined, and the infinite
eigenvalue corresponds to .
The generalized symmetric definite eigenproblem in section 2.3.7
has only finite real eigenvalues. The generalized nonsymmetric
eigenvalue problem can have real, complex or infinite eigenvalues.
To deal with both finite (including zero) and infinite
eigenvalues, the LAPACK routines return two values,
and .
If
is non-zero then
is an eigenvalue.
If
is zero then
is an eigenvalue of **(***A*, *B*).
(Round off may change an exactly zero
to a small nonzero value,
changing the eigenvalue
to some very large value;
see section 4.11 for details.)
A basic task of these
routines is to compute all *n* pairs
and *x* and/or
*y* for a given pair of matrices **(***A*,*B*).

If the determinant of
is identically
zero for all values of ,
the eigenvalue problem is called **singular**; otherwise it is **regular**.
Singularity of **(***A*,*B*) 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 (see section 4.11.1.4 for further
discussion)
[93,105,29,53].

Another basic task is to compute the **generalized Schur decomposition**
of the pair **(***A*,*B*). If *A* and *B* are complex, then their generalized
Schur decomposition is *A* = *QSZ*^{H} and *B* = *QTZ*^{H}, where *Q* and *Z* are
unitary and *S* and *T* are upper triangular. The LAPACK routines
normalize *T* to have real non-negative diagonal entries.
Note that in this
form, the eigenvalues can be easily computed from the diagonals:
(if )
and
(if *t*_{ii} = 0), and so the LAPACK
routines return
and
.

The generalized Schur form depends on the order of the eigenvalues on the
diagonal of **(***S*,*T*). This order may optionally be chosen by the user.

If *A* and *B* are real, then their generalized Schur decomposition
is *A* = *QSZ*^{T} and *B* = *QTZ*^{T}, where *Q* and *Z* are orthogonal,
*S* is quasi-upper triangular with 1-by-1 and 2-by-2 blocks on the
diagonal, and *T* is upper triangular with non-negative diagonal entries.
The structure of a typical pair of **(***S*,*T*) is illustrated below for *n*=6:

The **1 x 1** diagonal blocks of **(***S*,*T*)
(those in the (1,1) and (4,4) positions)
contain the real eigenvalues of **(***A*,*B*) and
the **2 x 2** diagonal blocks of **(***S*,*T*)
(those in the (2:3,2:3) and (5:6,5:6) positions)
contain conjugate pairs of complex eigenvalues of **(***A*,*B*).
The **2 x 2** diagonal blocks of *T* corresponding to 2-by-2
blocks of *S* are made diagonal.
This arrangement enables us to work entirely with real numbers, even when
some of the eigenvalues of **(***A*,*B*) are complex.
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 diagonals of *S* and *T*. The
and
values corresponding to complex eigenvalues
of a 2-by-2 diagonal block of **(***S*,*T*)
are computed by first
computing the complex conjugate eigenvalues
and
of the block,
then computing the values of
and
that would
result if the block were put into *complex* generalized
Schur form, 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* [94].
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 left corner of *S* and *T* as explained
in section 2.3.5.2.

The computations proceed in the following stages:

- 1.
- The pair
**(***A*,*B*) is reduced to **generalized upper Hessenberg form**.
If *A* and *B* are real, this decomposition is *A* = *UHV*^{T}
and *B* = *U R V*^{T} where *H* is upper Hessenberg (zero below the
first subdiagonal), *R* is upper triangular, and *U* and *V*
are orthogonal. If *A* and *B* are complex, the decomposition is
*A* = *UHV*^{H} and *B* = *URV*^{H} with *U* and *V* unitary, and *H*
and *R* as before. This decomposition is performed by the
subroutine xGGHRD,
which computes *H* and *R*, 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.

- 2.
- The pair
**(***H*,*R*) is reduced to generalized Schur form
*H* = *QSZ*^{T} and *R* = *QTZ*^{T} (for *H* and *R* real) or
*H* = *QSZ*^{H} and *R* = *QTZ*^{H} (for *H* and *R* complex)
by subroutine xHGEQZ.
The values
and
are also
computed, where
are the
eigenvalues. The matrices *Z* and *Q* are optionally computed.

- 3.
- The left and/or right eigenvectors of the pair
**(***S*,*T*) are
computed by xTGEVC.
One may optionally transform the right
eigenvectors of **(***S*,*T*) to the right eigenvectors of **(***A*,*B*)
(or of **(***H*,*R*)) by passing **(***UQ*,*VZ*) (or **(***Q*,*Z*)) to xTGEVC.

Other subsidiary tasks may be performed before or after
those described.

** Next:** Balancing
** Up:** Generalized Nonsymmetric Eigenproblems
** Previous:** Generalized Nonsymmetric Eigenproblems
** Contents**
** Index**
*Susan Blackford*

*1999-10-01*