f02 Chapter Contents
f02 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_eigen_real_gen_quad (f02jcc)

## 1  Purpose

 $λ2 ⁢ A + λ ⁢ B + C ⁢ x = 0 ,$
where $A$, $B$ and $C$ are real $n$ by $n$ matrices.
The function returns the $2n$ eigenvalues, ${\lambda }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,2n$, and can optionally return the corresponding right eigenvectors, ${x}_{j}$ and/or left eigenvectors, ${y}_{j}$ as well as estimates of the condition numbers of the computed eigenvalues and backward errors of the computed right and left eigenvectors. A left eigenvector satisfies the equation
 $yH ⁢ λ2⁢A+ λ⁢B+ C = 0 ,$
where ${y}^{\mathrm{H}}$ is the complex conjugate transpose of $y$.
$\lambda$ is represented as the pair $\left(\alpha ,\beta \right)$, such that $\lambda =\alpha /\beta$. Note that the computation of $\alpha /\beta$ may overflow and indeed $\beta$ may be zero.

## 2  Specification

 #include #include
 void nag_eigen_real_gen_quad (Nag_ScaleType scal, Nag_LeftVecsType jobvl, Nag_RightVecsType jobvr, Nag_CondErrType sense, double tol, Integer n, double a[], Integer pda, double b[], Integer pdb, double c[], Integer pdc, double alphar[], double alphai[], double beta[], double vl[], Integer pdvl, double vr[], Integer pdvr, double s[], double bevl[], double bevr[], Integer *iwarn, NagError *fail)

## 3  Description

The quadratic eigenvalue problem is solved by linearizing the problem and solving the resulting $2n$ by $2n$ generalized eigenvalue problem. The linearization is chosen to have favourable conditioning and backward stability properties. An initial preprocessing step is performed that reveals and deflates the zero and infinite eigenvalues contributed by singular leading and trailing matrices.
The algorithm is backward stable for problems that are not too heavily damped, that is $‖B‖\le \sqrt{‖A‖·‖C‖}$.
Further details on the algorithm are given in Hammarling et al. (2013).

## 4  References

Fan H -Y, Lin W.-W and Van Dooren P. (2004) Normwise scaling of second order polynomial matrices. SIAM J. Matrix Anal. Appl. 26, 1 252–256
Gaubert S and Sharify M (2009) Tropical scaling of polynomial matrices Lecture Notes in Control and Information Sciences Series 389 291–303 Springer–Verlag
Hammarling S, Munro C J and Tisseur F (2013) An algorithm for the complete solution of quadratic eigenvalue problems. ACM Trans. Math. Software. 39(3):18:1–18:119 (http://eprints.ma.man.ac.uk/1815/)

## 5  Arguments

1:     scalNag_ScaleTypeInput
On entry: determines the form of scaling to be performed on $A$, $B$ and $C$.
${\mathbf{scal}}=\mathrm{Nag_NoScale}$
No scaling.
${\mathbf{scal}}=\mathrm{Nag_CondFanLinVanDooren}$ (the recommended value)
Fan, Lin and Van Dooren scaling if $\frac{‖B‖}{\sqrt{‖A‖×‖C‖}}<10$ and no scaling otherwise where $‖Z‖$ is the Frobenius norm of $Z$.
${\mathbf{scal}}=\mathrm{Nag_FanLinVanDooren}$
Fan, Lin and Van Dooren scaling.
${\mathbf{scal}}=\mathrm{Nag_TropicalLargest}$
Tropical scaling with largest root.
${\mathbf{scal}}=\mathrm{Nag_TropicalSmallest}$
Tropical scaling with smallest root.
Constraint: ${\mathbf{scal}}=\mathrm{Nag_NoScale}$, $\mathrm{Nag_CondFanLinVanDooren}$, $\mathrm{Nag_FanLinVanDooren}$, $\mathrm{Nag_TropicalLargest}$ or $\mathrm{Nag_TropicalSmallest}$.
2:     jobvlNag_LeftVecsTypeInput
On entry: if ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$, do not compute left eigenvectors.
If ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, compute the left eigenvectors.
If ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$, jobvl must be set to $\mathrm{Nag_LeftVecs}$.
Constraint: ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$ or $\mathrm{Nag_LeftVecs}$.
3:     jobvrNag_RightVecsTypeInput
On entry: if ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$, do not compute right eigenvectors.
If ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, compute the right eigenvectors.
If ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrRight}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$, jobvr must be set to $\mathrm{Nag_RightVecs}$.
Constraint: ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$ or $\mathrm{Nag_RightVecs}$.
4:     senseNag_CondErrTypeInput
On entry: determines whether, or not, condition numbers and backward errors are computed.
${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$
Do not compute condition numbers, or backward errors.
${\mathbf{sense}}=\mathrm{Nag_CondOnly}$
Just compute condition numbers for the eigenvalues.
${\mathbf{sense}}=\mathrm{Nag_BackErrLeft}$
Just compute backward errors for the left eigenpairs.
${\mathbf{sense}}=\mathrm{Nag_BackErrRight}$
Just compute backward errors for the right eigenpairs.
${\mathbf{sense}}=\mathrm{Nag_BackErrBoth}$
Compute backward errors for the left and right eigenpairs.
${\mathbf{sense}}=\mathrm{Nag_CondBackErrLeft}$
Compute condition numbers for the eigenvalues and backward errors for the left eigenpairs.
${\mathbf{sense}}=\mathrm{Nag_CondBackErrRight}$
Compute condition numbers for the eigenvalues and backward errors for the right eigenpairs.
${\mathbf{sense}}=\mathrm{Nag_CondBackErrBoth}$
Compute condition numbers for the eigenvalues and backward errors for the left and right eigenpairs.
Constraint: ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$, $\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrRight}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$.
5:     toldoubleInput
On entry: tol is used as the tolerance for making decisions on rank in the deflation procedure. If tol is zero on entry then  is used in place of tol, where $‖Z‖$ is the Frobenius norm of the (scaled) matrix $Z$ and machine precision is as returned by function nag_machine_precision (X02AJC). If tol is $-1.0$ on entry then no deflation is attempted. The recommended value for tol is zero.
6:     nIntegerInput
On entry: the order of the matrices $A$, $B$ and $C$.
Constraint: ${\mathbf{n}}\ge 0$.
7:     a[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array a must be at least ${\mathbf{pda}}×{\mathbf{n}}$.
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]$.
On entry: the $n$ by $n$ matrix $A$.
On exit: a is used as internal workspace, but if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$ or ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, then a is restored on exit.
8:     pdaIntegerInput
On entry: the stride separating matrix row elements in the array a.
Constraint: ${\mathbf{pda}}\ge {\mathbf{n}}$.
9:     b[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array b must be at least ${\mathbf{pdb}}×{\mathbf{n}}$.
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]$.
On entry: the $n$ by $n$ matrix $B$.
On exit: b is used as internal workspace, but is restored on exit.
10:   pdbIntegerInput
On entry: the stride separating matrix row elements in the array b.
Constraint: ${\mathbf{pdb}}\ge {\mathbf{n}}$.
11:   c[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array c must be at least ${\mathbf{pdc}}×{\mathbf{n}}$.
The $\left(i,j\right)$th element of the matrix $C$ is stored in ${\mathbf{c}}\left[\left(j-1\right)×{\mathbf{pdc}}+i-1\right]$.
On entry: the $n$ by $n$ matrix $C$.
On exit: c is used as internal workspace, but if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$ or ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, c is restored on exit.
12:   pdcIntegerInput
On entry: the stride separating matrix row elements in the array c.
Constraint: ${\mathbf{pdc}}\ge {\mathbf{n}}$.
13:   alphar[$2×{\mathbf{n}}$]doubleOutput
On exit: ${\mathbf{alphar}}\left[\mathit{j}-1\right]$, for $\mathit{j}=1,2,\dots ,2n$, contains the real part of ${\alpha }_{j}$ for the $j$th eigenvalue pair $\left({\alpha }_{j},{\beta }_{j}\right)$ of the quadratic eigenvalue problem.
14:   alphai[$2×{\mathbf{n}}$]doubleOutput
On exit: ${\mathbf{alphai}}\left[\mathit{j}-1\right]$, for $\mathit{j}=1,2,\dots ,2n$, contains the imaginary part of ${\alpha }_{j}$ for the $j$th eigenvalue pair $\left({\alpha }_{j},{\beta }_{j}\right)$ of the quadratic eigenvalue problem. If ${\mathbf{alphai}}\left[j-1\right]$ is zero then the $j$th eigenvalue is real; if ${\mathbf{alphai}}\left[j-1\right]$ is positive then the $j$th and $\left(j+1\right)$th eigenvalues are a complex conjugate pair, with ${\mathbf{alphai}}\left[j\right]$ negative.
15:   beta[$2×{\mathbf{n}}$]doubleOutput
On exit: ${\mathbf{beta}}\left[\mathit{j}-1\right]$, for $\mathit{j}=1,2,\dots ,2n$, contains the second part of the $j$th eigenvalue pair $\left({\alpha }_{j},{\beta }_{j}\right)$ of the quadratic eigenvalue problem, with ${\beta }_{j}\ge 0$. Infinite eigenvalues have ${\beta }_{j}$ set to zero.
16:   vl[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array vl must be at least $2×{\mathbf{n}}$ when ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$.
Where ${\mathbf{VL}}\left(i,j\right)$ appears in this document, it refers to the array element ${\mathbf{vl}}\left[\left(j-1\right)×{\mathbf{pdvl}}+i-1\right]$.
On exit: if ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, the left eigenvectors ${y}_{j}$ are stored one after another in vl, in the same order as the corresponding eigenvalues. If the $j$th eigenvalue is real, then ${y}_{j}={\mathbf{VL}}\left(:,j\right)$, the $j$th column of VL. If the $j$th and $\left(j+1\right)$th eigenvalues form a complex conjugate pair, then ${y}_{j}={\mathbf{VL}}\left(:,j\right)+i×{\mathbf{VL}}\left(:,j+1\right)$ and ${y}_{j+1}={\mathbf{VL}}\left(:,j\right)-i×{\mathbf{VL}}\left(:,j+1\right)$. Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$, vl is not referenced and may be NULL.
17:   pdvlIntegerInput
On entry: the stride separating matrix row elements in the array vl.
Constraint: ${\mathbf{pdvl}}\ge {\mathbf{n}}$.
18:   vr[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array vr must be at least $2×{\mathbf{n}}$ when ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$.
Where ${\mathbf{VR}}\left(i,j\right)$ appears in this document, it refers to the array element ${\mathbf{vr}}\left[\left(j-1\right)×{\mathbf{pdvr}}+i-1\right]$.
On exit: if ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, the right eigenvectors ${x}_{j}$ are stored one after another in vr, in the same order as the corresponding eigenvalues. If the $j$th eigenvalue is real, then ${x}_{j}={\mathbf{VR}}\left(:,j\right)$, the $j$th column of VR. If the $j$th and $\left(j+1\right)$th eigenvalues form a complex conjugate pair, then ${x}_{j}={\mathbf{VR}}\left(:,j\right)+i×{\mathbf{VR}}\left(:,j+1\right)$ and ${x}_{j+1}={\mathbf{VR}}\left(:,j\right)-i×{\mathbf{VR}}\left(:,j+1\right)$. Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$, vr is not referenced and may be NULL.
19:   pdvrIntegerInput
On entry: the stride separating matrix row elements in the array vr.
Constraint: ${\mathbf{pdvr}}\ge {\mathbf{n}}$.
20:   s[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array s must be at least $2×{\mathbf{n}}$ when ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$.
Also: computing the condition numbers of the eigenvalues requires that both the left and right eigenvectors be computed.
On exit: if ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$, ${\mathbf{s}}\left[j-1\right]$ contains the condition number estimate for the $j$th eigenvalue (large condition numbers imply that the problem is near one with multiple eigenvalues). Infinite condition numbers are returned as the largest model double number (nag_real_largest_number (X02ALC)).
If ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$, $\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrRight}$ or $\mathrm{Nag_BackErrBoth}$, s is not referenced and may be NULL.
21:   bevl[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array bevl must be at least $2×{\mathbf{n}}$ when ${\mathbf{sense}}=\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$ or $\mathrm{Nag_CondBackErrBoth}$.
On exit: if ${\mathbf{sense}}=\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$ or $\mathrm{Nag_CondBackErrBoth}$, ${\mathbf{bevl}}\left[j-1\right]$ contains the backward error estimate for the computed left eigenpair $\left({\lambda }_{j},{y}_{j}\right)$.
If ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$, $\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrRight}$ or $\mathrm{Nag_CondBackErrRight}$, bevl is not referenced and may be NULL.
22:   bevr[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array bevr must be at least $2×{\mathbf{n}}$ when ${\mathbf{sense}}=\mathrm{Nag_BackErrRight}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$.
On exit: if ${\mathbf{sense}}=\mathrm{Nag_BackErrRight}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$, ${\mathbf{bevr}}\left[j-1\right]$ contains the backward error estimate for the computed right eigenpair $\left({\lambda }_{j},{x}_{j}\right)$.
If ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$, $\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrLeft}$ or $\mathrm{Nag_CondBackErrLeft}$, bevr is not referenced and may be NULL.
23:   iwarnInteger *Output
On exit: iwarn will be positive if there are warnings, otherwise iwarn will be $0$.
If ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR then:
• if ${\mathbf{iwarn}}=1$ then one, or both, of the matrices $A$ and $C$ is zero. In this case no scaling is performed, even if ${\mathbf{scal}}>0$;
• if ${\mathbf{iwarn}}=2$ then the matrices $A$ and $C$ are singular, or nearly singular, so the problem is potentially ill-posed;
• if ${\mathbf{iwarn}}=3$ then both the conditions for ${\mathbf{iwarn}}=1$ and ${\mathbf{iwarn}}=2$ above, apply.
If ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ITERATIONS_QZ, nag_dgges (f08xac) has flagged that iwarn eigenvalues are invalid.
If ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_ITERATIONS_QZ, nag_dggev (f08wac) has flagged that iwarn eigenvalues are invalid.
24:   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_ARRAY_SIZE
On entry, ${\mathbf{pda}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pda}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{pdb}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdb}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{pdc}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdc}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{pdvl}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{jobvl}}=⟨\mathit{\text{value}}⟩$.
Constraint: when ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, ${\mathbf{pdvl}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{pdvr}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{jobvr}}=⟨\mathit{\text{value}}⟩$.
Constraint: when ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, ${\mathbf{pdvr}}\ge {\mathbf{n}}$.
On entry, argument $⟨\mathit{\text{value}}⟩$ had an illegal value.
NE_INT
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 0$.
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_INVALID_VALUE
On entry, ${\mathbf{sense}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{jobvl}}=⟨\mathit{\text{value}}⟩$.
Constraint: when ${\mathbf{jobvl}}=\mathrm{Nag_NotLeftVecs}$, ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$ or $\mathrm{Nag_BackErrRight}$,
when ${\mathbf{jobvl}}=\mathrm{Nag_LeftVecs}$, ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrLeft}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$.
On entry, ${\mathbf{sense}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{jobvr}}=⟨\mathit{\text{value}}⟩$.
Constraint: when ${\mathbf{jobvr}}=\mathrm{Nag_NotRightVecs}$, ${\mathbf{sense}}=\mathrm{Nag_NoCondBackErr}$ or $\mathrm{Nag_BackErrLeft}$,
when ${\mathbf{jobvr}}=\mathrm{Nag_RightVecs}$, ${\mathbf{sense}}=\mathrm{Nag_CondOnly}$, $\mathrm{Nag_BackErrRight}$, $\mathrm{Nag_BackErrBoth}$, $\mathrm{Nag_CondBackErrLeft}$, $\mathrm{Nag_CondBackErrRight}$ or $\mathrm{Nag_CondBackErrBoth}$.
NE_ITERATIONS_QZ
The $QZ$ iteration failed in nag_dggev (f08wac).
iwarn returns the value of info returned by nag_dggev (f08wac). This failure is unlikely to happen, but if it does, please contact NAG.
The $QZ$ iteration failed in nag_dgges (f08xac).
iwarn returns the value of info returned by nag_dgges (f08xac). This failure is unlikely to happen, but if it does, please contact NAG.
NE_SINGULAR
The quadratic matrix polynomial is nonregular (singular).

## 7  Accuracy

The algorithm is backward stable for problems that are not too heavily damped, that is $‖B‖\le \sqrt{‖A‖·‖C‖}$.

## 8  Parallelism and Performance

nag_eigen_real_gen_quad (f02jcc) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

None.

## 10  Example

To solve the quadratic eigenvalue problem
 $λ2 A + λB + C x = 0$
where
 $A = 1 2 2 3 1 1 3 2 1 , B = 3 2 1 2 1 3 1 3 2 and C = 1 1 2 2 3 1 3 1 2 .$
The example also returns the left eigenvectors, condition numbers for the computed eigenvalues and backward errors of the computed right and left eigenpairs.

### 10.1  Program Text

Program Text (f02jcce.c)

### 10.2  Program Data

Program Data (f02jcce.d)

### 10.3  Program Results

Program Results (f02jcce.r)