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_lapack_dstedc (f08jh)

 Contents

    1  Purpose
    2  Syntax
    7  Accuracy
    9  Example

Purpose

nag_lapack_dstedc (f08jh) computes all the eigenvalues and, optionally, all the eigenvectors of a real n by n symmetric tridiagonal matrix, or of a real full or banded symmetric matrix which has been reduced to tridiagonal form.

Syntax

[d, e, z, info] = f08jh(compz, d, e, z, 'n', n)
[d, e, z, info] = nag_lapack_dstedc(compz, d, e, z, 'n', n)

Description

nag_lapack_dstedc (f08jh) computes all the eigenvalues and, optionally, the eigenvectors of a real symmetric tridiagonal matrix T. That is, the function computes the spectral factorization of T given by
T = Z Λ ZT ,  
where Λ is a diagonal matrix whose diagonal elements are the eigenvalues, λi, of T and Z is an orthogonal matrix whose columns are the eigenvectors, zi, of T. Thus
Tzi = λi zi ,   i = 1,2,,n .  
The function may also be used to compute all the eigenvalues and vectors of a real full, or banded, symmetric matrix A which has been reduced to tridiagonal form T as
A = QTQT ,  
where Q is orthogonal. The spectral factorization of A is then given by
A = QZ Λ QZT .  
In this case Q must be formed explicitly and passed to nag_lapack_dstedc (f08jh) in the array z, and the function called with compz='V'. Functions which may be called to form T and Q are
full matrix nag_lapack_dsytrd (f08fe) and nag_lapack_dorgtr (f08ff)
full matrix, packed storage nag_lapack_dsptrd (f08ge) and nag_lapack_dopgtr (f08gf)
band matrix nag_lapack_dsbtrd (f08he), with vect='V'
When only eigenvalues are required then this function calls nag_lapack_dsterf (f08jf) to compute the eigenvalues of the tridiagonal matrix T, but when eigenvectors of T are also required and the matrix is not too small, then a divide and conquer method is used, which can be much faster than nag_lapack_dsteqr (f08je), although more storage is required.

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

Parameters

Compulsory Input Parameters

1:     compz – string (length ≥ 1)
Indicates whether the eigenvectors are to be computed.
compz='N'
Only the eigenvalues are computed (and the array z is not referenced).
compz='V'
The eigenvalues and eigenvectors of A are computed (and the array z must contain the matrix Q on entry).
compz='I'
The eigenvalues and eigenvectors of T are computed (and the array z is initialized by the function).
Constraint: compz='N', 'V' or 'I'.
2:     d: – double array
The dimension of the array d must be at least max1,n
The diagonal elements of the tridiagonal matrix.
3:     e: – double array
The dimension of the array e must be at least max1,n-1
The subdiagonal elements of the tridiagonal matrix.
4:     zldz: – double array
The first dimension, ldz, of the array z must satisfy
  • if compz='V' or 'I', ldz max1,n ;
  • otherwise ldz1.
The second dimension of the array z must be at least max1,n if compz='V' or 'I', and at least 1 otherwise.
If compz='V', z must contain the orthogonal matrix Q used in the reduction to tridiagonal form.

Optional Input Parameters

1:     n int64int32nag_int scalar
Default: the dimension of the array d.
n, the order of the symmetric tridiagonal matrix T.
Constraint: n0.

Output Parameters

1:     d: – double array
The dimension of the array d will be max1,n
If info=0, the eigenvalues in ascending order.
2:     e: – double array
The dimension of the array e will be max1,n-1
3:     zldz: – double array
The first dimension, ldz, of the array z will be
  • if compz='V' or 'I', ldz= max1,n ;
  • otherwise ldz=1.
The second dimension of the array z will be max1,n if compz='V' or 'I' and 1 otherwise.
If compz='V', z contains the orthonormal eigenvectors of the original symmetric matrix A, and if compz='I', z contains the orthonormal eigenvectors of the symmetric tridiagonal matrix T.
If compz='N', z is not referenced.
4:     info int64int32nag_int scalar
info=0 unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

   info=-i
If info=-i, parameter i had an illegal value on entry. The parameters are numbered as follows:
1: compz, 2: n, 3: d, 4: e, 5: z, 6: ldz, 7: work, 8: lwork, 9: iwork, 10: liwork, 11: info.
It is possible that info refers to a parameter that is omitted from the MATLAB interface. This usually indicates that an error in one of the other input parameters has caused an incorrect value to be inferred.
W  info>0
The algorithm failed to compute an eigenvalue while working on the submatrix lying in rows and columns info/n+1 through info mod n+1.

Accuracy

The computed eigenvalues and eigenvectors are exact for a nearby matrix T+E, where
E2 = Oε T2 ,  
and ε is the machine precision.
If λi is an exact eigenvalue and λ~i is the corresponding computed value, then
λ~i - λi c n ε T2 ,  
where cn is a modestly increasing function of n.
If zi is the corresponding exact eigenvector, and z~i is the corresponding computed eigenvector, then the angle θz~i,zi between them is bounded as follows:
θ z~i,zi cnεT2 minijλi-λj .  
Thus the accuracy of a computed eigenvector depends on the gap between its eigenvalue and all the other eigenvalues.
See Section 4.7 of Anderson et al. (1999) for further details. See also nag_lapack_ddisna (f08fl).

Further Comments

If only eigenvalues are required, the total number of floating-point operations is approximately proportional to n2. When eigenvectors are required the number of operations is bounded above by approximately the same number of operations as nag_lapack_dsteqr (f08je), but for large matrices nag_lapack_dstedc (f08jh) is usually much faster.
The complex analogue of this function is nag_lapack_zstedc (f08jv).

Example

This example finds all the eigenvalues and eigenvectors of the symmetric band matrix
A = 4.99 0.04 0.22 0.00 0.04 1.05 -0.79 1.04 0.22 -0.79 -2.31 -1.30 0.00 1.04 -1.30 -0.43 .  
A is first reduced to tridiagonal form by a call to nag_lapack_dsbtrd (f08he).
function f08jh_example


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

% Symmetric band matrix A, stored on symmetric banded format
uplo = 'L';
kd   = int64(2);
n    = int64(4);
ab   = [4.99,  1.05, -2.31, -0.43;
        0.04, -0.79, -1.30,  0;
        0.22,  1.04,  0,     0];

% Reduce A to tridiagonal form and compute Q
vect = 'V';
q = zeros(n, n);
[apf, d, e, q, info] = f08he( ...
                              vect, uplo, kd, ab, q);

% Calculate eigenvalues and eigenvectors of A
compz = 'V';
[w, ~, z, info] = f08jh( ...
                         compz, d, e, q);

% Normalize eigenvectors: largest element positive
for j = 1:n
  [~,k] = max(abs(z(:,j)));
  if z(k,j) < 0;
    z(:,j) = -z(:,j);
  end
end                            

disp('Eigenvalues');
disp(w');
disp('Eigenvectors');
disp(z);


f08jh example results

Eigenvalues
   -2.9943   -0.7000    1.9974    4.9969

Eigenvectors
   -0.0251    0.0162    0.0113    0.9995
    0.0656   -0.5859    0.8077    0.0020
    0.9002   -0.3135   -0.3006    0.0311
    0.4298    0.7471    0.5070   -0.0071


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