hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_eigen_real_gen_quad (f02jc)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

nag_eigen_real_gen_quad (f02jc) solves the quadratic eigenvalue problem
λ2 A + λ B + C x = 0 ,  
where A, B and C are real n by n matrices.
The function returns the 2n eigenvalues, λj, for j=1,2,,2n, and can optionally return the corresponding right eigenvectors, xj and/or left eigenvectors, yj 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 λ2A+ λB+ C = 0 ,  
where yH is the complex conjugate transpose of y.
λ is represented as the pair α,β , such that λ = α/β. Note that the computation of α/β may overflow and indeed β may be zero.

Syntax

[a, b, c, alphar, alphai, beta, vl, vr, s, bevl, bevr, iwarn, ifail] = f02jc(scal, jobvl, jobvr, sense, tol, a, b, c, 'n', n)
[a, b, c, alphar, alphai, beta, vl, vr, s, bevl, bevr, iwarn, ifail] = nag_eigen_real_gen_quad(scal, jobvl, jobvr, sense, tol, a, b, c, 'n', n)

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 BA·C.
Further details on the algorithm are given in Hammarling et al. (2013).

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/)

Parameters

Compulsory Input Parameters

1:     scal int64int32nag_int scalar
Determines the form of scaling to be performed on A, B and C.
scal=0
No scaling.
scal=1 (the recommended value)
Fan, Lin and Van Dooren scaling if B A×C <10  and no scaling otherwise where Z is the Frobenius norm of Z.
scal=2
Fan, Lin and Van Dooren scaling.
scal=3
Tropical scaling with largest root.
scal=4
Tropical scaling with smallest root.
Constraint: scal=0, 1, 2, 3 or 4.
2:     jobvl – string (length ≥ 1)
If jobvl='N', do not compute left eigenvectors.
If jobvl='V', compute the left eigenvectors.
If sense=1, 2, 4, 5, 6 or 7, jobvl must be set to 'V'.
Constraint: jobvl='N' or 'V'.
3:     jobvr – string (length ≥ 1)
If jobvr='N', do not compute right eigenvectors.
If jobvr='V', compute the right eigenvectors.
If sense=1, 3, 4, 5, 6 or 7, jobvr must be set to 'V'.
Constraint: jobvr='N' or 'V'.
4:     sense int64int32nag_int scalar
Determines whether, or not, condition numbers and backward errors are computed.
sense=0
Do not compute condition numbers, or backward errors.
sense=1
Just compute condition numbers for the eigenvalues.
sense=2
Just compute backward errors for the left eigenpairs.
sense=3
Just compute backward errors for the right eigenpairs.
sense=4
Compute backward errors for the left and right eigenpairs.
sense=5
Compute condition numbers for the eigenvalues and backward errors for the left eigenpairs.
sense=6
Compute condition numbers for the eigenvalues and backward errors for the right eigenpairs.
sense=7
Compute condition numbers for the eigenvalues and backward errors for the left and right eigenpairs.
Constraint: sense=0, 1, 2, 3, 4, 5, 6 or 7.
5:     tol – double scalar
tol is used as the tolerance for making decisions on rank in the deflation procedure. If tol is zero on entry then n× maxA,B,C × machine precision  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 (x02aj). If tol is -1.0 on entry then no deflation is attempted. The recommended value for tol is zero.
6:     alda: – double array
The first dimension of the array a must be at least n.
The second dimension of the array a must be at least n.
The n by n matrix A.
7:     bldb: – double array
The first dimension of the array b must be at least n.
The second dimension of the array b must be at least n.
The n by n matrix B.
8:     cldc: – double array
The first dimension of the array c must be at least n.
The second dimension of the array c must be at least n.
The n by n matrix C.

Optional Input Parameters

1:     n int64int32nag_int scalar
Default: the second dimension of the arrays a, b, c and the first dimension of the arrays a, b, c. (An error is raised if these dimensions are not equal.)
The order of the matrices A, B and C.
Constraint: n0.

Output Parameters

1:     alda: – double array
The first dimension of the array a will be n.
The second dimension of the array a will be n.
a is used as internal workspace, but if jobvl='V' or jobvr='V', then a is restored on exit.
2:     bldb: – double array
The first dimension of the array b will be n.
The second dimension of the array b will be n.
b is used as internal workspace, but is restored on exit.
3:     cldc: – double array
The first dimension of the array c will be n.
The second dimension of the array c will be n.
c is used as internal workspace, but if jobvl='V' or jobvr='V', c is restored on exit.
4:     alphar2×n – double array
alpharj, for j=1,2,,2n, contains the real part of αj for the jth eigenvalue pair αj,βj of the quadratic eigenvalue problem.
5:     alphai2×n – double array
alphaij, for j=1,2,,2n, contains the imaginary part of αj for the jth eigenvalue pair αj,βj of the quadratic eigenvalue problem. If alphaij is zero then the jth eigenvalue is real; if alphaij is positive then the jth and j+1th eigenvalues are a complex conjugate pair, with alphaij+1 negative.
6:     beta2×n – double array
betaj, for j=1,2,,2n, contains the second part of the jth eigenvalue pair αj,βj of the quadratic eigenvalue problem, with βj0. Infinite eigenvalues have βj set to zero.
7:     vlldvl: – double array
The first dimension of the array vl will be n.
The second dimension of the array vl will be 2×n if jobvl='V'.
If jobvl='V', the left eigenvectors yj are stored one after another in the columns of vl, in the same order as the corresponding eigenvalues. If the jth eigenvalue is real, then yj=vl:j, the jth column of vl. If the jth and j+1th eigenvalues form a complex conjugate pair, then yj= vl:j + i× vl:j+1 and yj+1 = vl:j -i × vl:j+1 . Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If jobvl='N', vl is not referenced.
8:     vrldvr: – double array
The first dimension of the array vr will be n.
The second dimension of the array vr will be 2×n if jobvr='V'.
If jobvr='V', the right eigenvectors xj are stored one after another in the columns of vr, in the same order as the corresponding eigenvalues. If the jth eigenvalue is real, then xj = vr:j , the jth column of vr. If the jth and j+1th eigenvalues form a complex conjugate pair, then xj = vr:j +i× vr:j+1 and xj+1= vr:j -i× vr:j+1 . Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If jobvr='N', vr is not referenced.
9:     s: – double array
The dimension of the array s will be 2×n if sense=1, 5, 6 or 7
Note: also: computing the condition numbers of the eigenvalues requires that both the left and right eigenvectors be computed.
If sense=1, 5, 6 or 7, sj contains the condition number estimate for the jth 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_machine_real_largest (x02al)).
If sense=0, 2, 3 or 4, s is not referenced.
10:   bevl: – double array
The dimension of the array bevl will be 2×n if sense=2, 4, 5 or 7
If sense=2, 4, 5 or 7, bevlj contains the backward error estimate for the computed left eigenpair λj,yj .
If sense=0, 1, 3 or 6, bevl is not referenced.
11:   bevr: – double array
The dimension of the array bevr will be 2×n if sense=3, 4, 6 or 7
If sense=3, 4, 6 or 7, bevrj contains the backward error estimate for the computed right eigenpair λj,xj .
If sense=0, 1, 2 or 5, bevr is not referenced.
12:   iwarn int64int32nag_int scalar
iwarn will be positive if there are warnings, otherwise iwarn will be 0.
If ifail=0 then:
  • if iwarn=1 then one, or both, of the matrices A and C is zero. In this case no scaling is performed, even if scal>0;
  • if iwarn=2 then the matrices A and C are singular, or nearly singular, so the problem is potentially ill-posed;
  • if iwarn=3 then both the conditions for iwarn=1 and iwarn=2 above, apply.
If ifail=2, iwarn returns the value of info from nag_lapack_dgges (f08xa).
If ifail=3, iwarn returns the value of info from nag_lapack_dggev (f08wa).
13:   ifail int64int32nag_int scalar
ifail=0 unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:
   ifail=1
The quadratic matrix polynomial is nonregular (singular).
   ifail=2
The QZ iteration failed in nag_lapack_dgges (f08xa).
iwarn returns the value of info returned by nag_lapack_dgges (f08xa). This failure is unlikely to happen, but if it does, please contact NAG.
   ifail=3
The QZ iteration failed in nag_lapack_dggev (f08wa).
iwarn returns the value of info returned by nag_lapack_dggev (f08wa). This failure is unlikely to happen, but if it does, please contact NAG.
   ifail=-1
Constraint: scal=0, 1, 2, 3 or 4.
   ifail=-2
Constraint: when jobvl='N', sense=0 or 3,
when jobvl='V', sense=1, 2, 4, 5, 6 or 7.
On entry, jobvl=_.
Constraint: jobvl='N' or 'V'.
   ifail=-3
Constraint: when jobvr='N', sense=0 or 2,
when jobvr='V', sense=1, 3, 4, 5, 6 or 7.
On entry, jobvr=_.
Constraint: jobvr='N' or 'V'.
   ifail=-4
Constraint: sense=0, 1, 2, 3, 4, 5, 6 or 7.
   ifail=-6
Constraint: n0.
   ifail=-8
Constraint: ldan.
   ifail=-10
Constraint: ldbn.
   ifail=-12
Constraint: ldcn.
   ifail=-17
Constraint: when jobvl='V', ldvln.
   ifail=-19
Constraint: when jobvr='V', ldvrn.
   ifail=-99
An unexpected error has been triggered by this routine. Please contact NAG.
   ifail=-399
Your licence key may have expired or may not have been installed correctly.
   ifail=-999
Dynamic memory allocation failed.

Accuracy

The algorithm is backward stable for problems that are not too heavily damped, that is B A·C .

Further Comments

None.

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.
function f02jc_example


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

% Solve quadratic eigenvalue problem defined by A, B and C:

a = [ 1 2 2;
      3 1 1;
      3 2 1];

b = [ 3 2 1;
      2 1 3;
      1 3 2];

c = [ 1 1 2;
      2 3 1;
      3 1 2];

% Use default scaling and compute eigenvalue condition numbers and
% backward errors for both left and right eigenpairs
scal  = int64(1);
sense = int64(7);
tol   = 0;
[a, b, c, alphar, alphai, beta, vl, vr, s, bevl, bevr, iwarn, ifail] = ...
  f02jc(...
        scal, 'V', 'V', sense, tol, a, b, c);

eigv = complex(alphar+alphai*i)./beta;
disp('Eigenvalues:');
disp(eigv);
[ifail] = x04ca('General', ' ', vr, 'Right eigenvectors:');
disp(' ');
[ifail] = x04ca('General', ' ', vl, 'Left eigenvectors:');
disp(' ');
disp('Eigenvalue condition numbers:');
disp(s);
fprintf('\nMaximum backward errors for eigenvalues and\n');
fprintf('%30s eigenvectors: %7.2e\n', 'right', max(bevr));
fprintf('%30s eigenvectors: %7.2e\n', 'left', max(bevl));


f02jc example results

Eigenvalues:
  -3.8513 + 0.0000i
  -0.5922 + 0.8028i
  -0.5922 - 0.8028i
   0.5233 + 0.6225i
   0.5233 - 0.6225i
   0.7891 + 0.0000i

 Right eigenvectors:
          1       2       3       4       5       6
 1  -0.2108  0.3751 -0.1877 -0.6593  0.0424 -0.3478
 2   0.7695  0.5020 -0.2433  0.0302  0.0197  0.8277
 3  -0.6028  0.7162  0.0000  0.7498  0.0000 -0.4405
 
 Left eigenvectors:
          1       2       3       4       5       6
 1   0.1052  0.7816  0.0000  0.8079  0.0000  0.0358
 2   0.7381  0.5075 -0.1352 -0.1124 -0.0314  0.7072
 3  -0.6664  0.3202 -0.1038 -0.5704  0.0913 -0.7061
 
Eigenvalue condition numbers:
    2.3092
    0.7027
    0.7027
    2.7013
    2.7013
    2.0144


Maximum backward errors for eigenvalues and
                         right eigenvectors: 4.85e-16
                          left eigenvectors: 5.18e-16

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015