The algebraic and analytic theory of the generalized eigenvalue problem is considerably more complicated than the corresponding theory of the standard eigenvalue problem. This has been discussed in §2.6. This chapter covers a variety of numerical techniques for treating different sorts of the generalized eigenvalue problems.
In §8.2, a brief sketch of what is called the QZ algorithm
for the generalized eigenvalue problem is presented. This is currently
the most powerful method for dense problems and it is an analog of the
QR algorithm. However, the QZ method is only
suitable for small- to moderate-sized problems because of
the requirements of floating point operations and
memory
locations.
A common approach for a large scale generalized eigenvalue problem
is to reduce the problem (8.1) or (8.2) to
a standard eigenvalue
problem and then apply an iterative method, as described in
Chapter 7. We refer to this technique
as reduction to standard form. This reduction to standard form
requires, for each iteration, the solution of a linear system with
or
or a combination of
and
. This will be discussed in more
detail in §8.3.
The Jacobi-Davidson method, presented in §8.4, avoids
the transformation of
to a standard eigenproblem.
It does not need the exact solution of a linear system, only that
a preconditioned iteration be available for a system with the
matrix
, which offers possibilities to
improve overall efficiency.
The rational Krylov algorithm, introduced in §8.5, is a further development of shifted and inverted Arnoldi. It combines the bases from several shifts to find all eigenvalues in a prescribed region of the complex plane. This is of special interest when one wants to know the response of a linear dynamic system over a large range of frequencies.
In §8.6, a pseudosymmetric Lanczos method is
presented for a special type of the
generalized eigenvalue problem (8.1), namely, where the
matrices and
are real symmetric, but neither
nor
nor a combination
, for real numbers
and
,
is positive definite.
is called
a symmetric indefinite matrix pencil.
The symmetry of
and
is an algebraic property and it is
not sufficient to ensure any of the special
mathematical properties of a definite matrix pencil. Therefore,
we cannot immediately use the algorithms described in Chapter 5.
The pseudosymmetric Lanczos algorithm described in §8.6
can save about half of the memory requirements and floating point operations.
However, without special precautions this technique could be numerically
unstable.
In §8.7,
a software package called GUPTRI is presented,
which is designed for the singular generalized eigenvalue
problem, that is, when
the characteristic polynomial
is identical to zero for all
. This happens, for example, when
and
have a common null space.
The algorithms described in this section are efficient for
small and dense problems. The costs of algorithms are of order
.
In the final section, 8.8, tools to assess the accuracy of computed eigenvalues and corresponding eigenvectors of the regular GNHEP are discussed.