Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_lapack_dhgeqz (f08xe)

## Purpose

nag_lapack_dhgeqz (f08xe) implements the $QZ$ method for finding generalized eigenvalues of the real matrix pair $\left(A,B\right)$ of order $n$, which is in the generalized upper Hessenberg form.

## Syntax

[a, b, alphar, alphai, beta, q, z, info] = f08xe(job, compq, compz, ilo, ihi, a, b, q, z, 'n', n)
[a, b, alphar, alphai, beta, q, z, info] = nag_lapack_dhgeqz(job, compq, compz, ilo, ihi, a, b, q, z, 'n', n)

## Description

nag_lapack_dhgeqz (f08xe) implements a single-double-shift version of the $QZ$ method for finding the generalized eigenvalues of the real matrix pair $\left(A,B\right)$ which is in the generalized upper Hessenberg form. If the matrix pair $\left(A,B\right)$ is not in the generalized upper Hessenberg form, then the function nag_lapack_dgghrd (f08we) should be called before invoking nag_lapack_dhgeqz (f08xe).
This problem is mathematically equivalent to solving the equation
 $detA-λB=0.$
Note that, to avoid underflow, overflow and other arithmetic problems, the generalized eigenvalues ${\lambda }_{j}$ are never computed explicitly by this function but defined as ratios between two computed values, ${\alpha }_{j}$ and ${\beta }_{j}$:
 $λj=αj/βj.$
The arguments ${\alpha }_{j}$, in general, are finite complex values and ${\beta }_{j}$ are finite real non-negative values.
If desired, the matrix pair $\left(A,B\right)$ may be reduced to generalized Schur form. That is, the transformed matrix $B$ is upper triangular and the transformed matrix $A$ is block upper triangular, where the diagonal blocks are either $1$ by $1$ or $2$ by $2$. The $1$ by $1$ blocks provide generalized eigenvalues which are real and the $2$ by $2$ blocks give complex generalized eigenvalues.
The argument job specifies two options. If ${\mathbf{job}}=\text{'S'}$ then the matrix pair $\left(A,B\right)$ is simultaneously reduced to Schur form by applying one orthogonal transformation (usually called $Q$) on the left and another (usually called $Z$) on the right. That is,
 $A←QTAZ B←QTBZ$
The $2$ by $2$ upper-triangular diagonal blocks of $B$ corresponding to $2$ by $2$ blocks of a will be reduced to non-negative diagonal matrices. That is, if ${\mathbf{a}}\left(j+1,j\right)$ is nonzero, then ${\mathbf{b}}\left(j+1,j\right)={\mathbf{b}}\left(j,j+1\right)=0$ and ${\mathbf{b}}\left(j,j\right)$ and ${\mathbf{b}}\left(j+1,j+1\right)$ will be non-negative.
If ${\mathbf{job}}=\text{'E'}$, then at each iteration the same transformations are computed but they are only applied to those parts of $A$ and $B$ which are needed to compute $\alpha$ and $\beta$. This option could be used if generalized eigenvalues are required but not generalized eigenvectors.
If ${\mathbf{job}}=\text{'S'}$ and ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$, and ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, then the orthogonal transformations used to reduce the pair $\left(A,B\right)$ are accumulated into the input arrays q and z. If generalized eigenvectors are required then job must be set to ${\mathbf{job}}=\text{'S'}$ and if left (right) generalized eigenvectors are to be computed then compq (compz) must be set to ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$ and not ${\mathbf{compq}}\ne \text{'N'}$.
If ${\mathbf{compq}}=\text{'I'}$, then eigenvectors are accumulated on the identity matrix and on exit the array q contains the left eigenvector matrix $Q$. However, if ${\mathbf{compq}}=\text{'V'}$ then the transformations are accumulated on the user-supplied matrix ${Q}_{0}$ in array q on entry and thus on exit q contains the matrix product $Q{Q}_{0}$. A similar convention is used for compz.

## References

Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Moler C B and Stewart G W (1973) An algorithm for generalized matrix eigenproblems SIAM J. Numer. Anal. 10 241–256
Stewart G W and Sun J-G (1990) Matrix Perturbation Theory Academic Press, London

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{job}$ – string (length ≥ 1)
Specifies the operations to be performed on $\left(A,B\right)$.
${\mathbf{job}}=\text{'E'}$
The matrix pair $\left(A,B\right)$ on exit might not be in the generalized Schur form.
${\mathbf{job}}=\text{'S'}$
The matrix pair $\left(A,B\right)$ on exit will be in the generalized Schur form.
Constraint: ${\mathbf{job}}=\text{'E'}$ or $\text{'S'}$.
2:     $\mathrm{compq}$ – string (length ≥ 1)
Specifies the operations to be performed on $Q$:
${\mathbf{compq}}=\text{'N'}$
The array q is unchanged.
${\mathbf{compq}}=\text{'V'}$
The left transformation $Q$ is accumulated on the array q.
${\mathbf{compq}}=\text{'I'}$
The array q is initialized to the identity matrix before the left transformation $Q$ is accumulated in q.
Constraint: ${\mathbf{compq}}=\text{'N'}$, $\text{'V'}$ or $\text{'I'}$.
3:     $\mathrm{compz}$ – string (length ≥ 1)
Specifies the operations to be performed on $Z$.
${\mathbf{compz}}=\text{'N'}$
The array z is unchanged.
${\mathbf{compz}}=\text{'V'}$
The right transformation $Z$ is accumulated on the array z.
${\mathbf{compz}}=\text{'I'}$
The array z is initialized to the identity matrix before the right transformation $Z$ is accumulated in z.
Constraint: ${\mathbf{compz}}=\text{'N'}$, $\text{'V'}$ or $\text{'I'}$.
4:     $\mathrm{ilo}$int64int32nag_int scalar
5:     $\mathrm{ihi}$int64int32nag_int scalar
The indices ${i}_{\mathrm{lo}}$ and ${i}_{\mathrm{hi}}$, respectively which define the upper triangular parts of $A$. The submatrices $A\left(1:{i}_{\mathrm{lo}}-1,1:{i}_{\mathrm{lo}}-1\right)$ and $A\left({i}_{\mathrm{hi}}+1:n,{i}_{\mathrm{hi}}+1:n\right)$ are then upper triangular. These arguments are provided by nag_lapack_dggbal (f08wh) if the matrix pair was previously balanced; otherwise, ${\mathbf{ilo}}=1$ and ${\mathbf{ihi}}={\mathbf{n}}$.
Constraints:
• if ${\mathbf{n}}>0$, $1\le {\mathbf{ilo}}\le {\mathbf{ihi}}\le {\mathbf{n}}$;
• if ${\mathbf{n}}=0$, ${\mathbf{ilo}}=1$ and ${\mathbf{ihi}}=0$.
6:     $\mathrm{a}\left(\mathit{lda},:\right)$ – double array
The first dimension of the array a must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array a must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The $n$ by $n$ upper Hessenberg matrix $A$. The elements below the first subdiagonal must be set to zero.
7:     $\mathrm{b}\left(\mathit{ldb},:\right)$ – double array
The first dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The $n$ by $n$ upper triangular matrix $B$. The elements below the diagonal must be zero.
8:     $\mathrm{q}\left(\mathit{ldq},:\right)$ – double array
The first dimension, $\mathit{ldq}$, of the array q must satisfy
• if ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldq}\ge {\mathbf{n}}$;
• if ${\mathbf{compq}}=\text{'N'}$, $\mathit{ldq}\ge 1$.
The second dimension of the array q must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$ and at least $1$ if ${\mathbf{compq}}=\text{'N'}$.
If ${\mathbf{compq}}=\text{'V'}$, the matrix ${Q}_{0}$. The matrix ${Q}_{0}$ is usually the matrix $Q$ returned by nag_lapack_dgghrd (f08we).
If ${\mathbf{compq}}=\text{'N'}$, q is not referenced.
9:     $\mathrm{z}\left(\mathit{ldz},:\right)$ – double array
The first dimension, $\mathit{ldz}$, of the array z must satisfy
• if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldz}\ge {\mathbf{n}}$;
• if ${\mathbf{compz}}=\text{'N'}$, $\mathit{ldz}\ge 1$.
The second dimension of the array z must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$ and at least $1$ if ${\mathbf{compz}}=\text{'N'}$.
If ${\mathbf{compz}}=\text{'V'}$, the matrix ${Z}_{0}$. The matrix ${Z}_{0}$ is usually the matrix $Z$ returned by nag_lapack_dgghrd (f08we).
If ${\mathbf{compz}}=\text{'N'}$, z is not referenced.

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the second dimension of the arrays a, b, q, z and the first dimension of the arrays a, b, q, z. (An error is raised if these dimensions are not equal.)
$n$, the order of the matrices $A$, $B$, $Q$ and $Z$.
Constraint: ${\mathbf{n}}\ge 0$.

### Output Parameters

1:     $\mathrm{a}\left(\mathit{lda},:\right)$ – double array
The first dimension of the array a will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array a will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
If ${\mathbf{job}}=\text{'S'}$, the matrix pair $\left(A,B\right)$ will be simultaneously reduced to generalized Schur form.
If ${\mathbf{job}}=\text{'E'}$, the $1$ by $1$ and $2$ by $2$ diagonal blocks of the matrix pair $\left(A,B\right)$ will give generalized eigenvalues but the remaining elements will be irrelevant.
2:     $\mathrm{b}\left(\mathit{ldb},:\right)$ – double array
The first dimension of the array b will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
The second dimension of the array b will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
If ${\mathbf{job}}=\text{'S'}$, the matrix pair $\left(A,B\right)$ will be simultaneously reduced to generalized Schur form.
If ${\mathbf{job}}=\text{'E'}$, the $1$ by $1$ and $2$ by $2$ diagonal blocks of the matrix pair $\left(A,B\right)$ will give generalized eigenvalues but the remaining elements will be irrelevant.
3:     $\mathrm{alphar}\left({\mathbf{n}}\right)$ – double array
The real parts of ${\alpha }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$.
4:     $\mathrm{alphai}\left({\mathbf{n}}\right)$ – double array
The imaginary parts of ${\alpha }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$.
5:     $\mathrm{beta}\left({\mathbf{n}}\right)$ – double array
${\beta }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$.
6:     $\mathrm{q}\left(\mathit{ldq},:\right)$ – double array
The first dimension, $\mathit{ldq}$, of the array q will be
• if ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldq}={\mathbf{n}}$;
• if ${\mathbf{compq}}=\text{'N'}$, $\mathit{ldq}=1$.
The second dimension of the array q will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compq}}=\text{'V'}$ or $\text{'I'}$ and at least $1$ if ${\mathbf{compq}}=\text{'N'}$.
If ${\mathbf{compq}}=\text{'V'}$, q contains the matrix product $Q{Q}_{0}$.
If ${\mathbf{compq}}=\text{'I'}$, q contains the transformation matrix $Q$.
7:     $\mathrm{z}\left(\mathit{ldz},:\right)$ – double array
The first dimension, $\mathit{ldz}$, of the array z will be
• if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldz}={\mathbf{n}}$;
• if ${\mathbf{compz}}=\text{'N'}$, $\mathit{ldz}=1$.
The second dimension of the array z will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$ and at least $1$ if ${\mathbf{compz}}=\text{'N'}$.
If ${\mathbf{compz}}=\text{'V'}$, z contains the matrix product $Z{Z}_{0}$.
If ${\mathbf{compz}}=\text{'I'}$, z contains the transformation matrix $Z$.
8:     $\mathrm{info}$int64int32nag_int scalar
${\mathbf{info}}=0$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

${\mathbf{info}}=-i$
If ${\mathbf{info}}=-i$, parameter $i$ had an illegal value on entry. The parameters are numbered as follows:
1: job, 2: compq, 3: compz, 4: n, 5: ilo, 6: ihi, 7: a, 8: lda, 9: b, 10: ldb, 11: alphar, 12: alphai, 13: beta, 14: q, 15: ldq, 16: z, 17: ldz, 18: work, 19: lwork, 20: info.
It is possible that info refers to a parameter that is omitted from the MATLAB interface. This usually indicates that an error in one of the other input parameters has caused an incorrect value to be inferred.
W  ${\mathbf{info}}>0$
If $1\le {\mathbf{info}}\le {\mathbf{n}}$, the $QZ$ iteration did not converge and the matrix pair $\left(A,B\right)$ is not in the generalized Schur form at exit. However, if ${\mathbf{info}}<{\mathbf{n}}$, then the computed ${\alpha }_{i}$ and ${\beta }_{i}$ should be correct for $i={\mathbf{info}}+1,\dots ,{\mathbf{n}}$.
If ${\mathbf{n}}+1\le {\mathbf{info}}\le 2×{\mathbf{n}}$, the computation of shifts failed and the matrix pair $\left(A,B\right)$ is not in the generalized Schur form at exit. However, if ${\mathbf{info}}<2×{\mathbf{n}}$, then the computed ${\alpha }_{i}$ and ${\beta }_{i}$ should be correct for $i={\mathbf{info}}-{\mathbf{n}}+1,\dots ,{\mathbf{n}}$.
If ${\mathbf{info}}>2×{\mathbf{n}}$, then an unexpected Library error has occurred. Please contact NAG with details of your program.

## Accuracy

Please consult Section 4.11 of the LAPACK Users' Guide (see Anderson et al. (1999)) and Chapter 6 of Stewart and Sun (1990), for more information.

nag_lapack_dhgeqz (f08xe) is the fifth step in the solution of the real generalized eigenvalue problem and is called after nag_lapack_dgghrd (f08we).
The complex analogue of this function is nag_lapack_zhgeqz (f08xs).

## Example

This example computes the $\alpha$ and $\beta$ arguments, which defines the generalized eigenvalues, of the matrix pair $\left(A,B\right)$ given by
 $A = 1.0 1.0 1.0 1.0 1.0 2.0 4.0 8.0 16.0 32.0 3.0 9.0 27.0 81.0 243.0 4.0 16.0 64.0 256.0 1024.0 5.0 25.0 125.0 625.0 3125.0$
 $B = 1.0 2.0 3.0 4.0 5.0 1.0 4.0 9.0 16.0 25.0 1.0 8.0 27.0 64.0 125.0 1.0 16.0 81.0 256.0 625.0 1.0 32.0 243.0 1024.0 3125.0 .$
This requires calls to five functions: nag_lapack_dggbal (f08wh) to balance the matrix, nag_lapack_dgeqrf (f08ae) to perform the $QR$ factorization of $B$, nag_lapack_dormqr (f08ag) to apply $Q$ to $A$, nag_lapack_dgghrd (f08we) to reduce the matrix pair to the generalized Hessenberg form and nag_lapack_dhgeqz (f08xe) to compute the eigenvalues using the $QZ$ algorithm.
```function f08xe_example

fprintf('f08xe example results\n\n');

a = [ 1.0   1.0    1.0    1.0     1.0;
2.0   4.0    8.0   16.0    32.0;
3.0   9.0   27.0   81.0   243.0;
4.0  16.0   64.0  256.0  1024.0;
5.0  25.0  125.0  625.0  3125.0];
b = a';

%' Balance A and B
job = 'B';
[a, b, ilo, ihi, lscale, rscale, info] = ...
f08wh(job, a, b);

bbal = b(ilo:ihi,ilo:ihi);
abal = a(ilo:ihi,ilo:ihi);

% QR factorize balanced B
[QR, tau, info] = f08ae(bbal);

% Perform C = Q^T*A
side = 'Left';
trans = 'Transpose';
[c, info] = f08ag(...
side, trans, QR, tau, abal);

% Generalized Hessenberg form (C,R) -> (H,T)
compq = 'No Q';
compz = 'No Z';
z = eye(4);
q = eye(4);
jlo = int64(1);
jhi = int64(ihi-ilo+1);
[H, T, ~, ~, info] = ...
f08we(...
compq, compz, jlo, jhi, c, QR, q, z);

% Find eigenvalues of generalized Hessenberg form
%    = eigenvalues of (A,B).
job = 'Eigenvalues';
[~, ~, alphar, alphai, beta, ~, ~, info] = ...
f08xe(...
job, compq, compz, jlo, jhi, H, T, q, z);

disp('Generalized eigenvalues of (A,B):');
w = complex(alphar+i*alphai);
disp(w./beta);

```
```f08xe example results

Generalized eigenvalues of (A,B):
-2.4367 + 0.0000i
0.6069 + 0.7948i
0.6069 - 0.7948i
1.0000 + 0.0000i
-0.4104 + 0.0000i

```