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:

- and are first simultaneously reduced to condensed forms by unitary equivalence transformations. More specifically, is reduced to upper Hessenberg form and is reduced to upper triangular form (Schur form). The trick is now to reduce also to upper Schur form, while keeping in that form. This is accomplished in the next step.
- The effect of one shifted QR step on (without forming that matrix product) is simulated by unitary equivalence transformations and on the matrix pair and ; this is the heart of the QZ iteration. If applied iteratively, it reduces to triangular or quasi-triangular form (that is, with by blocks along the diagonal, in order to avoid complex arithmetic), while preserving the triangular structure of . At convergence, we have the generalized Schur form of and (see §2.6); that is, we have computed orthogonal and so that and are upper triangular.
- 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 to the eigenvectors of the original problem.

The QZ algorithm leads to all eigenvalues and, optionally, to the right and left eigenvectors. It requires floating point operations and memory locations, where is the order of and . More specifically, it requires about floating point operations for computing the eigenvalues only. If right eigenvectors are desired, then an additional 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.