nag_dggev (f08wac) (PDF version)
f08 Chapter Contents
f08 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_dggev (f08wac)

## 1  Purpose

nag_dggev (f08wac) computes for a pair of $n$ by $n$ real nonsymmetric matrices $\left(A,B\right)$ the generalized eigenvalues and, optionally, the left and/or right generalized eigenvectors using the $QZ$ algorithm.

## 2  Specification

 #include #include
 void nag_dggev (Nag_OrderType order, Nag_LeftVecsType jobvl, Nag_RightVecsType jobvr, Integer n, double a[], Integer pda, double b[], Integer pdb, double alphar[], double alphai[], double beta[], double vl[], Integer pdvl, double vr[], Integer pdvr, NagError *fail)

## 3  Description

A generalized eigenvalue for a pair of matrices $\left(A,B\right)$ is a scalar $\lambda$ or a ratio $\alpha /\beta =\lambda$, such that $A-\lambda B$ is singular. It is usually represented as the pair $\left(\alpha ,\beta \right)$, as there is a reasonable interpretation for $\beta =0$, and even for both being zero.
The right eigenvector ${v}_{j}$ corresponding to the eigenvalue ${\lambda }_{j}$ of $\left(A,B\right)$ satisfies
 $A vj = λj B vj .$
The left eigenvector ${u}_{j}$ corresponding to the eigenvalue ${\lambda }_{j}$ of $\left(A,B\right)$ satisfies
 $ujH A = λj ujH B ,$
where ${u}_{j}^{\mathrm{H}}$ is the conjugate-transpose of ${u}_{j}$.
All the eigenvalues and, if required, all the eigenvectors of the generalized eigenproblem $Ax=\lambda Bx$, where $A$ and $B$ are real, square matrices, are determined using the $QZ$ algorithm. The $QZ$ algorithm consists of four stages:
1. $A$ is reduced to upper Hessenberg form and at the same time $B$ is reduced to upper triangular form.
2. $A$ is further reduced to quasi-triangular form while the triangular form of $B$ is maintained. This is the real generalized Schur form of the pair $\left(A,B\right)$.
3. The quasi-triangular form of $A$ is reduced to triangular form and the eigenvalues extracted. This function does not actually produce the eigenvalues ${\lambda }_{j}$, but instead returns ${\alpha }_{j}$ and ${\beta }_{j}$ such that
 $λj=αj/βj, j=1,2,…,n.$
The division by ${\beta }_{j}$ becomes your responsibility, since ${\beta }_{j}$ may be zero, indicating an infinite eigenvalue. Pairs of complex eigenvalues occur with ${\alpha }_{j}/{\beta }_{j}$ and ${\alpha }_{j+1}/{\beta }_{j+1}$ complex conjugates, even though ${\alpha }_{j}$ and ${\alpha }_{j+1}$ are not conjugate.
4. If the eigenvectors are required they are obtained from the triangular matrices and then transformed back into the original coordinate system.

## 4  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 http://www.netlib.org/lapack/lug
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Wilkinson J H (1979) Kronecker's canonical form and the $QZ$ algorithm Linear Algebra Appl. 28 285–303

## 5  Arguments

1:     orderNag_OrderTypeInput
On entry: the order argument specifies the two-dimensional storage scheme being used, i.e., row-major ordering or column-major ordering. C language defined storage is specified by ${\mathbf{order}}=\mathrm{Nag_RowMajor}$. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.
Constraint: ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ or Nag_ColMajor.
2:     jobvlNag_LeftVecsTypeInput
On entry: if ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$, do not compute the left generalized eigenvectors.
If ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, compute the left generalized eigenvectors.
Constraint: ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$ or $\mathrm{Nag_LeftVecs}$.
3:     jobvrNag_RightVecsTypeInput
On entry: if ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$, do not compute the right generalized eigenvectors.
If ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, compute the right generalized eigenvectors.
Constraint: ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$ or $\mathrm{Nag_RightVecs}$.
4:     nIntegerInput
On entry: $n$, the order of the matrices $A$ and $B$.
Constraint: ${\mathbf{n}}\ge 0$.
5:     a[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array a must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pda}}×{\mathbf{n}}\right)$.
The $\left(i,j\right)$th element of the matrix $A$ is stored in
• ${\mathbf{a}}\left[\left(j-1\right)×{\mathbf{pda}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{a}}\left[\left(i-1\right)×{\mathbf{pda}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On entry: the matrix $A$ in the pair $\left(A,B\right)$.
On exit: a has been overwritten.
6:     pdaIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array a.
Constraint: ${\mathbf{pda}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
7:     b[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array b must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdb}}×{\mathbf{n}}\right)$.
The $\left(i,j\right)$th element of the matrix $B$ is stored in
• ${\mathbf{b}}\left[\left(j-1\right)×{\mathbf{pdb}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{b}}\left[\left(i-1\right)×{\mathbf{pdb}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On entry: the matrix $B$ in the pair $\left(A,B\right)$.
On exit: b has been overwritten.
8:     pdbIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array b.
Constraint: ${\mathbf{pdb}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
9:     alphar[n]doubleOutput
On exit: the element ${\mathbf{alphar}}\left[j-1\right]$ contains the real part of ${\alpha }_{j}$.
10:   alphai[n]doubleOutput
On exit: the element ${\mathbf{alphai}}\left[j-1\right]$ contains the imaginary part of ${\alpha }_{j}$.
11:   beta[n]doubleOutput
On exit: $\left({\mathbf{alphar}}\left[\mathit{j}-1\right]+{\mathbf{alphai}}\left[\mathit{j}-1\right]×i\right)/{\mathbf{beta}}\left[\mathit{j}-1\right]$, for $\mathit{j}=1,2,\dots ,{\mathbf{n}}$, will be the generalized eigenvalues.
If ${\mathbf{alphai}}\left[j-1\right]$ is zero, then the $j$th eigenvalue is real; if positive, then the $j$th and $\left(j+1\right)$st eigenvalues are a complex conjugate pair, with ${\mathbf{alphai}}\left[j\right]$ negative.
Note:  the quotients ${\mathbf{alphar}}\left[j-1\right]/{\mathbf{beta}}\left[j-1\right]$ and ${\mathbf{alphai}}\left[j-1\right]/{\mathbf{beta}}\left[j-1\right]$ may easily overflow or underflow, and ${\mathbf{beta}}\left[j-1\right]$ may even be zero. Thus, you should avoid naively computing the ratio ${\alpha }_{j}/{\beta }_{j}$. However, $\mathrm{max}\left|{\alpha }_{j}\right|$ will always be less than and usually comparable with ${‖{\mathbf{a}}‖}_{2}$ in magnitude, and $\mathrm{max}\left|{\beta }_{j}\right|$ will always be less than and usually comparable with ${‖{\mathbf{b}}‖}_{2}$.
12:   vl[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array vl must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdvl}}×{\mathbf{n}}\right)$ when ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$;
• $1$ otherwise.
The $i$th element of the $j$th vector is stored in
• ${\mathbf{vl}}\left[\left(j-1\right)×{\mathbf{pdvl}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{vl}}\left[\left(i-1\right)×{\mathbf{pdvl}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, the left eigenvectors ${u}_{j}$ are stored one after another in the columns of vl, in the same order as the corresponding eigenvalues.
If the $j$th eigenvalue is real, then ${u}_{j}={\mathbf{VL}}\left(:,j\right)$, the $j$th column of ${\mathbf{vl}}$.
If the $j$th and $\left(j+1\right)$th eigenvalues form a complex conjugate pair, then ${u}_{j}={\mathbf{VL}}\left(:,j\right)+i×{\mathbf{VL}}\left(:,j+1\right)$ and $u\left(j+1\right)={\mathbf{VL}}\left(:,j\right)-i×{\mathbf{VL}}\left(:,j+1\right)$. Each eigenvector will be scaled so the largest component has $\left|\text{real part}\right|+\left|\text{imag. part}\right|=1$.
If ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$, vl is not referenced.
13:   pdvlIntegerInput
On entry: the stride used in the array vl.
Constraints:
• if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, ${\mathbf{pdvl}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise ${\mathbf{pdvl}}\ge 1$.
14:   vr[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array vr must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdvr}}×{\mathbf{n}}\right)$ when ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$;
• $1$ otherwise.
The $i$th element of the $j$th vector is stored in
• ${\mathbf{vr}}\left[\left(j-1\right)×{\mathbf{pdvr}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{vr}}\left[\left(i-1\right)×{\mathbf{pdvr}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: if ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, the right eigenvectors ${v}_{j}$ are stored one after another in the columns of vr, in the same order as the corresponding eigenvalues.
If the $j$th eigenvalue is real, then ${v}_{j}={\mathbf{VR}}\left(:,j\right)$, the $j$th column of $\mathrm{VR}$.
If the $j$th and $\left(j+1\right)$th eigenvalues form a complex conjugate pair, then ${v}_{j}={\mathbf{VR}}\left(:,j\right)+i×{\mathbf{VR}}\left(:,j+1\right)$ and ${v}_{j+1}={\mathbf{VR}}\left(:,j\right)-i×{\mathbf{VR}}\left(:,j+1\right)$. Each eigenvector will be scaled so the largest component has $\left|\text{real part}\right|+\left|\text{imag. part}\right|=1$.
If ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$, vr is not referenced.
15:   pdvrIntegerInput
On entry: the stride used in the array vr.
Constraints:
• if ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, ${\mathbf{pdvr}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise ${\mathbf{pdvr}}\ge 1$.
16:   failNagError *Input/Output
The NAG error argument (see Section 3.6 in the Essential Introduction).

## 6  Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
NE_BAD_PARAM
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_EIGENVECTORS
A failure occurred in nag_dtgevc (f08ykc) while computing generalized eigenvectors.
NE_ENUM_INT_2
On entry, ${\mathbf{jobvl}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdvl}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, ${\mathbf{pdvl}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
otherwise ${\mathbf{pdvl}}\ge 1$.
On entry, ${\mathbf{jobvr}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdvr}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, ${\mathbf{pdvr}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
otherwise ${\mathbf{pdvr}}\ge 1$.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pda}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pda}}>0$.
On entry, ${\mathbf{pdb}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdb}}>0$.
On entry, ${\mathbf{pdvl}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdvl}}>0$.
On entry, ${\mathbf{pdvr}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdvr}}>0$.
NE_INT_2
On entry, ${\mathbf{pda}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pda}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
On entry, ${\mathbf{pdb}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdb}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
NE_ITERATION_QZ
The $QZ$ iteration failed. No eigenvectors have been calculated but ${\mathbf{alphar}}\left[j\right]$, ${\mathbf{alphai}}\left[j\right]$, and ${\mathbf{beta}}\left[j\right]$ should be correct from element $〈\mathit{\text{value}}〉$.
The $QZ$ iteration failed with an unexpected error, please contact NAG.

## 7  Accuracy

The computed eigenvalues and eigenvectors are exact for a nearby matrices $\left(A+E\right)$ and $\left(B+F\right)$, where
 $E,F F = Oε A,B F ,$
and $\epsilon$ is the machine precision. See Section 4.11 of Anderson et al. (1999) for further details.
Note:  interpretation of results obtained with the $QZ$ algorithm often requires a clear understanding of the effects of small changes in the original data. These effects are reviewed in Wilkinson (1979), in relation to the significance of small values of ${\alpha }_{j}$ and ${\beta }_{j}$. It should be noted that if ${\alpha }_{j}$ and ${\beta }_{j}$ are both small for any $j$, it may be that no reliance can be placed on any of the computed eigenvalues ${\lambda }_{i}={\alpha }_{i}/{\beta }_{i}$. You are recommended to study Wilkinson (1979) and, if in difficulty, to seek expert advice on determining the sensitivity of the eigenvalues to perturbations in the data.

## 8  Further Comments

The total number of floating point operations is proportional to ${n}^{3}$.
The complex analogue of this function is nag_zggev (f08wnc).

## 9  Example

This example finds all the eigenvalues and right eigenvectors of the matrix pair $\left(A,B\right)$, where
 $A = 3.9 12.5 -34.5 -0.5 4.3 21.5 -47.5 7.5 4.3 21.5 -43.5 3.5 4.4 26.0 -46.0 6.0 and B= 1.0 2.0 -3.0 1.0 1.0 3.0 -5.0 4.0 1.0 3.0 -4.0 3.0 1.0 3.0 -4.0 4.0 .$

### 9.1  Program Text

Program Text (f08wace.c)

### 9.2  Program Data

Program Data (f08wace.d)

### 9.3  Program Results

Program Results (f08wace.r)

nag_dggev (f08wac) (PDF version)
f08 Chapter Contents
f08 Chapter Introduction
NAG C Library Manual