Introduction

This chapter is devoted to the numerical solution of the (right) generalized non-Hermitian eigenvalue problem (GNHEP)

$$A x = \lambda B x,$$ (214)

where $A$ and $B$ are general $n$ by $n$ matrices. Occasionally, one may also seek the solution of the left GNHEP

$$y^{\ast} A = \lambda y^{\ast} B.$$ (215)

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 $O(n^3)$ floating point operations and $O(n^2)$ 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 $A$ or $B$ or a combination of $A$ and $B$. This will be discussed in more detail in §8.3.

The Jacobi-Davidson method, presented in §8.4, avoids the transformation of $A{x}=\lambda B {x}$ 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 $A-\sigma B$, 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 $A$ and $B$ are real symmetric, but neither $A$ nor $B$ nor a combination $\alpha A + \beta B$, for real numbers $\alpha$ and $\beta$, is positive definite. $A - \lambda B$ is called a symmetric indefinite matrix pencil. The symmetry of $A$ and $B$ 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 $p(\lambda) = \mbox{det}(A - \lambda B)$ is identical to zero for all $\lambda$. This happens, for example, when $A$ and $B$ 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 $O(n^4)$.

In the final section, 8.8, tools to assess the accuracy of computed eigenvalues and corresponding eigenvectors of the regular GNHEP are discussed.