Direct Methods

The QZ algorithm is the method of choice for computing the GNHEP (8.1). The algorithm is an analog of the QR algorithm (see §7.3) for the generalized eigenvalue problem. It follows the pattern described for the QR algorithm:

1. $A$ and $B$ are first simultaneously reduced to condensed forms by unitary equivalence transformations. More specifically, $A$ is reduced to upper Hessenberg form and $B$ is reduced to upper triangular form (Schur form). The trick is now to reduce $A$ also to upper Schur form, while keeping $B$ in that form. This is accomplished in the next step.
2. The effect of one shifted QR step on $AB^{-1}$ (without forming that matrix product) is simulated by unitary equivalence transformations $Q$ and $Z$ on the matrix pair $A$ and $B$; this is the heart of the QZ iteration. If applied iteratively, it reduces $A$ to triangular or quasi-triangular form (that is, with $2$ by $2$ blocks along the diagonal, in order to avoid complex arithmetic), while preserving the triangular structure of $B$. At convergence, we have the generalized Schur form of $A$ and $B$ (see §2.6); that is, we have computed orthogonal $Q$ and $Z$ so that $QAZ$ and $QBZ$ are upper triangular.
3. Eigenvalues can be computed from the diagonals of the triangular form. Eigenvectors can be computed as the eigenvectors of the triangular problem and then transformed back with $Z$ to the eigenvectors of the original problem.

This brief sketch has necessarily left a number of important questions untreated. For more details, the reader should consult the literature: the original paper on the QZ algorithm is Moler and Stewart [328]; the QZ algorithm is also described in the textbooks by, for examples, Golub and Van Loan [198] or Demmel [114].

The QZ algorithm leads to all eigenvalues and, optionally, to the right and left eigenvectors. It requires $O(n^3)$ floating point operations and $O(n^2)$ memory locations, where $n$ is the order of $A$ and $B$. More specifically, it requires about $30 n^3$ floating point operations for computing the eigenvalues only. If right eigenvectors are desired, then an additional $16n^3$ are necessary, and likewise for the left eigenvectors. These estimates of work are based on the experience that about two QZ iterations per eigenvalue are sufficient (the convergence properties of QZ are about the same as for QR).

Subroutines that implement QZ algorithms are included in most linear algebra-related software packages. It is used as the eig(A,B) command in MATLAB.In LAPACK [12], the following driver routines are available for performing a variety of tasks:

xGGES: Computes generalized eigenvalues, the generalized Schur form, and optionally the left and/or right matrices of Schur vectors.

xGGESX: xGGES plus condition estimates of eigenvalues and deflating subspaces.

xGGEV: Generalized eigenvalues, and optionally the left and/or right generalized eigenvectors.

xGGEVX: xGGEV plus condition estimates for eigenvalues and eigenvectors.

The letter ${\tt x}$ stands for S or D for real single or double precision data types, or C or Z for complex single or double precision data types.