where and are general by matrices. Occasionally, one may also seek the solution of the

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.