NAG Library Function Document
nag_eigen_complex_gen_quad (f02jqc)
1 Purpose
nag_eigen_complex_gen_quad (f02jqc) solves the quadratic eigenvalue problem
where
,
and
are complex
by
matrices.
The function returns the
eigenvalues,
, for
, and can optionally return the corresponding right eigenvectors,
and/or left eigenvectors,
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
where
is the complex conjugate transpose of
.
is represented as the pair , such that . Note that the computation of may overflow and indeed may be zero.
2 Specification
#include <nag.h> |
#include <nagf02.h> |
void |
nag_eigen_complex_gen_quad (Nag_ScaleType scal,
Nag_LeftVecsType jobvl,
Nag_RightVecsType jobvr,
Nag_CondErrType sense,
double tol,
Integer n,
Complex a[],
Integer pda,
Complex b[],
Integer pdb,
Complex c[],
Integer pdc,
Complex alpha[],
Complex beta[],
Complex vl[],
Integer pdvl,
Complex 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 by 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 .
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:
scal – Nag_ScaleTypeInput
On entry: determines the form of scaling to be performed on
,
and
.
- No scaling.
- (the recommended value)
- Fan, Lin and Van Dooren scaling if and no scaling otherwise where is the Frobenius norm of .
- Fan, Lin and Van Dooren scaling.
- Tropical scaling with largest root.
- Tropical scaling with smallest root.
Constraint:
, , , or .
- 2:
jobvl – Nag_LeftVecsTypeInput
-
On entry: if
, do not compute left eigenvectors.
If , compute the left eigenvectors.
If
,
,
,
,
or
,
jobvl must be set to
.
Constraint:
or .
- 3:
jobvr – Nag_RightVecsTypeInput
-
On entry: if
, do not compute right eigenvectors.
If , compute the right eigenvectors.
If
,
,
,
,
or
,
jobvr must be set to
.
Constraint:
or .
- 4:
sense – Nag_CondErrTypeInput
-
On entry: determines whether, or not, condition numbers and backward errors are computed.
- Do not compute condition numbers, or backward errors.
- Just compute condition numbers for the eigenvalues.
- Just compute backward errors for the left eigenpairs.
- Just compute backward errors for the right eigenpairs.
- Compute backward errors for the left and right eigenpairs.
- Compute condition numbers for the eigenvalues and backward errors for the left eigenpairs.
- Compute condition numbers for the eigenvalues and backward errors for the right eigenpairs.
- Compute condition numbers for the eigenvalues and backward errors for the left and right eigenpairs.
Constraint:
, , , , , , or .
- 5:
tol – doubleInput
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
is the Frobenius norm of the (scaled) matrix
and
machine precision is as returned by function
nag_machine_precision (X02AJC). If
tol is
on entry then no deflation is attempted. The recommended value for
tol is zero.
- 6:
n – IntegerInput
On entry: the order of the matrices , and .
Constraint:
.
- 7:
a[] – ComplexInput/Output
-
Note: the dimension,
dim, of the array
a
must be at least
.
The th element of the matrix is stored in .
On entry: the by matrix .
On exit:
a is used as internal workspace, but if
or
, then
a is restored on exit.
- 8:
pda – IntegerInput
-
On entry: the stride separating matrix row elements in the array
a.
Constraint:
.
- 9:
b[] – ComplexInput/Output
-
Note: the dimension,
dim, of the array
b
must be at least
.
The th element of the matrix is stored in .
On entry: the by matrix .
On exit:
b is used as internal workspace, but is restored on exit.
- 10:
pdb – IntegerInput
-
On entry: the stride separating matrix row elements in the array
b.
Constraint:
.
- 11:
c[] – ComplexInput/Output
-
Note: the dimension,
dim, of the array
c
must be at least
.
The th element of the matrix is stored in .
On entry: the by matrix .
On exit:
c is used as internal workspace, but if
or
,
c is restored on exit.
- 12:
pdc – IntegerInput
-
On entry: the stride separating matrix row elements in the array
c.
Constraint:
.
- 13:
alpha[] – ComplexOutput
-
On exit: , for , contains the first part of the the th eigenvalue pair of the quadratic eigenvalue problem.
- 14:
beta[] – ComplexOutput
-
On exit:
, for
, contains the second part of the
th eigenvalue pair
of the quadratic eigenvalue problem. Although
beta is declared complex, it is actually real and non-negative. Infinite eigenvalues have
set to zero.
- 15:
vl[] – ComplexOutput
-
Note: the dimension,
dim, of the array
vl
must be at least
when
.
Where appears in this document, it refers to the array element
.
On exit: if
, the left eigenvectors
are stored one after another in
vl, in the same order as the corresponding eigenvalues. Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If
,
vl is not referenced and may be
NULL.
- 16:
pdvl – IntegerInput
-
On entry: the stride separating matrix row elements in the array
vl.
Constraint:
.
- 17:
vr[] – ComplexOutput
-
Note: the dimension,
dim, of the array
vr
must be at least
when
.
Where appears in this document, it refers to the array element
.
On exit: if
, the right eigenvectors
are stored one after another in
vr, in the same order as the corresponding eigenvalues. Each eigenvector will be normalized with length unity and with the element of largest modulus real and positive.
If
,
vr is not referenced and may be
NULL.
- 18:
pdvr – IntegerInput
-
On entry: the stride separating matrix row elements in the array
vr.
Constraint:
.
- 19:
s[] – doubleOutput
-
Note: the dimension,
dim, of the array
s
must be at least
when
,
,
or
.
Also: computing the condition numbers of the eigenvalues requires that both the left and right eigenvectors be computed.
On exit: if
,
,
or
,
contains the condition number estimate for the
th eigenvalue (large condition numbers imply that the problem is near one with multiple eigenvalues). Infinite condition numbers are returned as the largest model real number (
nag_real_largest_number (X02ALC)).
If
,
,
or
,
s is not referenced and may be
NULL.
- 20:
bevl[] – doubleOutput
-
Note: the dimension,
dim, of the array
bevl
must be at least
when
,
,
or
.
On exit: if
,
,
or
,
contains the backward error estimate for the computed left eigenpair
.
If
,
,
or
,
bevl is not referenced and may be
NULL.
- 21:
bevr[] – doubleOutput
-
Note: the dimension,
dim, of the array
bevr
must be at least
when
,
,
or
.
On exit: if
,
,
or
,
contains the backward error estimate for the computed right eigenpair
.
If
,
,
or
,
bevr is not referenced and may be
NULL.
- 22:
iwarn – Integer *Output
-
On exit:
iwarn will be positive if there are warnings, otherwise
iwarn will be
.
If
NE_NOERROR then:
- if then one, or both, of the matrices and is zero. In this case no scaling is performed, even if ;
- if then the matrices and are singular, or nearly singular, so the problem is potentially ill-posed;
- if then both the conditions for and above, apply.
If
NE_ITERATIONS_QZ,
nag_zgges (f08xnc) has flagged that
iwarn eigenvalues are invalid.
If
NE_ITERATIONS_QZ,
nag_zggev (f08wnc) has flagged that
iwarn eigenvalues are invalid.
- 23:
fail – NagError *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, and .
Constraint: .
On entry, and .
Constraint: .
On entry, and .
Constraint: .
On entry, , and .
Constraint: when , .
On entry, , and .
Constraint: when , .
- NE_BAD_PARAM
-
On entry, argument had an illegal value.
- NE_INT
-
On entry, .
Constraint: .
- 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, and .
Constraint: when , or ,
when , , , , , or .
On entry, and .
Constraint: when , or ,
when , , , , , or .
- NE_ITERATIONS_QZ
-
The
iteration failed in
nag_zggev (f08wnc).
iwarn returns the value of
info returned by
nag_zggev (f08wnc). This failure is unlikely to happen, but if it does, please contact
NAG.
The
iteration failed in
nag_zgges (f08xnc).
iwarn returns the value of
info returned by
nag_zgges (f08xnc). 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 .
8 Parallelism and Performance
nag_eigen_complex_gen_quad (f02jqc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_eigen_complex_gen_quad (f02jqc) 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.
Please consult the
Users' Note for your implementation for any additional implementation-specific information.
None.
10 Example
To solve the quadratic eigenvalue problem
where
The example also returns the left eigenvectors, condition numbers for the computed eigenvalues and the maximum backward errors of the computed right and left eigenpairs.
10.1 Program Text
Program Text (f02jqce.c)
10.2 Program Data
Program Data (f02jqce.d)
10.3 Program Results
Program Results (f02jqce.r)