NAG C Library Function Document

nag_real_eigensystem_sel (f02ecc)


nag_real_eigensystem_sel (f02ecc) computes selected eigenvalues and eigenvectors of a real general matrix.


#include <nag.h>
#include <nagf02.h>
void  nag_real_eigensystem_sel (Nag_Select_Eigenvalues crit, Integer n, double a[], Integer tda, double wl, double wu, Integer mest, Integer *m, Complex w[], Complex v[], Integer tdv, NagError *fail)


nag_real_eigensystem_sel (f02ecc) computes selected eigenvalues and the corresponding right eigenvectors of a real general matrix A :
Ax i = λ i x i .  
Eigenvalues λ i  may be selected either by modulus, satisfying:
w l λ i w u ,  
or by real part, satisfying:
w l Re λ i w u .  
Note that even though A  is real, λ i  and x i  may be complex. If x i  is an eigenvector corresponding to a complex eigenvalue λ i , then the complex conjugate vector x - i  is the eigenvector corresponding to the complex conjugate eigenvalue λ - i . The eigenvalues in a complex conjugate pair λ i  and λ - i  are either both selected or both not selected.


Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore


1:     crit Nag_Select_EigenvaluesInput
On entry: indicates the criterion for selecting eigenvalues:
  • if crit=Nag_Select_Modulus, then eigenvalues are selected according to their moduli: w l λ i w u .
  • if crit=Nag_Select_RealPart, then eigenvalues are selected according to their real parts: w l Re λ i w u .
Constraint: crit=Nag_Select_Modulus or Nag_Select_RealPart.
2:     n IntegerInput
On entry: n , the order of the matrix A .
Constraint: n0 .
3:     a[n×tda] doubleInput/Output
Note: the i,jth element of the matrix A is stored in a[i-1×tda+j-1].
On entry: the n  by n  general matrix A .
On exit: a contains the Hessenberg form of the balanced input matrix A  (see Section 9).
4:     tda IntegerInput
On entry: the stride separating matrix column elements in the array a.
Constraint: tda max1,n .
5:     wl doubleInput
6:     wu doubleInput
On entry: w l  and w u , the lower and upper bounds on the criterion for the selected eigenvalues.
Constraint: wu>wl .
7:     mest IntegerInput
On entry: mest must be an upper bound on m , the number of eigenvalues and eigenvectors selected. No eigenvectors are computed if mest<m .
Constraint: mest max1,m .
8:     m Integer *Output
On exit: m , the number of eigenvalues actually selected.
9:     w[max1,n] ComplexOutput
On exit: the first m elements of w hold the values of the selected eigenvalues; elements from the index m to n-1  contain the other eigenvalues. Complex conjugate pairs of eigenvalues are stored in consecutive elements of the array, with the eigenvalue having the positive imaginary part first.
10:   v[n×tdv] ComplexOutput
Note: the i,jth element of the matrix V is stored in v[i-1×tdv+j-1].
On exit: v contains the selected eigenvectors, with the i th column holding the eigenvector associated with the eigenvalue λ i  (stored in w[i-1] ).
11:   tdv IntegerInput
On entry: the stride separating matrix column elements in the array v.
Constraint: tdvmest .
12:   fail NagError *Input/Output
The NAG error argument (see Section 3.7 in How to Use the NAG Library and its Documentation).

Error Indicators and Warnings

On entry, wu=value  while wl=value . These arguments must satisfy wu>wl .
Dynamic memory allocation failed.
On entry, argument crit had an illegal value.
Inverse iteration failed to compute all the specified eigenvectors. If an eigenvector failed to converge, the corresponding column of v is set to zero.
On entry, tda=value  while n=value .
Constraint: tda max1,n .
On entry, tdv=value  while mest=value .
Constraint: tdv max1,mest .
On entry, mest=value.
Constraint: mest1.
On entry, n=value.
Constraint: n0.
The QR algorithm failed to compute all the eigenvalues. No eigenvectors have been computed.
There are more than mest eigenvalues in the specified range. The actual number of eigenvalues in the range is returned in m. No eigenvectors have been computed.
Rerun with the second dimension of v = mest m .


If λ i  is an exact eigenvalue, and λ ~ i  is the corresponding computed value, then
λ ~ i - λ i c n ε A 2 s i ,  
where c n  is a modestly increasing function of n , ε  is the machine precision, and s i  is the reciprocal condition number of λ i ; A  is the balanced form of the original matrix A , and A A .
If x i  is the corresponding exact eigenvector, and x ~ i  is the corresponding computed eigenvector, then the angle θ x ~ i , x i  between them is bounded as follows:
θ x ~ i , x i c n ε A 2 sep i  
where sep i  is the reciprocal condition number of x i .

Parallelism and Performance

nag_real_eigensystem_sel (f02ecc) is not threaded in any implementation.

Further Comments

nag_real_eigensystem_sel (f02ecc) first balances the matrix, using a diagonal similarity transformation to reduce its norm; and then reduces the balanced matrix A  to upper Hessenberg form H , using an orthogonal similarity transformation: A = QHQT . The function uses the Hessenberg QR  algorithm to compute all the eigenvalues of H , which are the same as the eigenvalues of A . It computes the eigenvectors of H  which correspond to the selected eigenvalues, using inverse iteration. It premultiplies the eigenvectors by Q  to form the eigenvectors of A ; and finally transforms the eigenvectors to those of the original matrix A .
Each eigenvector x  (real or complex) is normalized so that x 2 = 1 , and the element of largest absolute value is real and positive.
The inverse iteration function may make a small perturbation to the real parts of close eigenvalues, and this may shift their moduli just outside the specified bounds. If you are relying on eigenvalues being within the bounds, you should test them on return from nag_real_eigensystem_sel (f02ecc).
The time taken by the function is approximately proportional to n 3 .
The function can be used to compute all eigenvalues and eigenvectors, by setting wl large and negative, and wu large and positive.


To compute those eigenvalues of the matrix A  whose moduli lie in the range 0.2,0.5 , and their corresponding eigenvectors, where
A = 0.35 0.45 -0.14 -0.17 0.09 0.07 -0.54 0.35 -0.44 -0.33 -0.03 0.17 0.25 -0.32 -0.13 0.11  

Program Text

Program Text (f02ecce.c)

Program Data

Program Data (f02ecce.d)

Program Results

Program Results (f02ecce.r)