Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_lapack_dstedc (f08jh)

## 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 $\Lambda$ is a diagonal matrix whose diagonal elements are the eigenvalues, ${\lambda }_{i}$, of $T$ and $Z$ is an orthogonal matrix whose columns are the eigenvectors, ${z}_{i}$, 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 ${\mathbf{compz}}=\text{'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 ${\mathbf{vect}}=\text{'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:     $\mathrm{compz}$ – string (length ≥ 1)
Indicates whether the eigenvectors are to be computed.
${\mathbf{compz}}=\text{'N'}$
Only the eigenvalues are computed (and the array z is not referenced).
${\mathbf{compz}}=\text{'V'}$
The eigenvalues and eigenvectors of $A$ are computed (and the array z must contain the matrix $Q$ on entry).
${\mathbf{compz}}=\text{'I'}$
The eigenvalues and eigenvectors of $T$ are computed (and the array z is initialized by the function).
Constraint: ${\mathbf{compz}}=\text{'N'}$, $\text{'V'}$ or $\text{'I'}$.
2:     $\mathrm{d}\left(:\right)$ – double array
The dimension of the array d must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
The diagonal elements of the tridiagonal matrix.
3:     $\mathrm{e}\left(:\right)$ – double array
The dimension of the array e must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}-1\right)$
The subdiagonal elements of the tridiagonal matrix.
4:     $\mathrm{z}\left(\mathit{ldz},:\right)$ – double array
The first dimension, $\mathit{ldz}$, of the array z must satisfy
• if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldz}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise $\mathit{ldz}\ge 1$.
The second dimension of the array z must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, and at least $1$ otherwise.
If ${\mathbf{compz}}=\text{'V'}$, z must contain the orthogonal matrix $Q$ used in the reduction to tridiagonal form.

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the dimension of the array d.
$n$, the order of the symmetric tridiagonal matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$.

### Output Parameters

1:     $\mathrm{d}\left(:\right)$ – double array
The dimension of the array d will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$
If ${\mathbf{info}}={\mathbf{0}}$, the eigenvalues in ascending order.
2:     $\mathrm{e}\left(:\right)$ – double array
The dimension of the array e will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}-1\right)$
3:     $\mathrm{z}\left(\mathit{ldz},:\right)$ – double array
The first dimension, $\mathit{ldz}$, of the array z will be
• if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, $\mathit{ldz}=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise $\mathit{ldz}=1$.
The second dimension of the array z will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$ if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$ and $1$ otherwise.
If ${\mathbf{compz}}=\text{'V'}$, z contains the orthonormal eigenvectors of the original symmetric matrix $A$, and if ${\mathbf{compz}}=\text{'I'}$, z contains the orthonormal eigenvectors of the symmetric tridiagonal matrix $T$.
If ${\mathbf{compz}}=\text{'N'}$, z is not referenced.
4:     $\mathrm{info}$int64int32nag_int scalar
${\mathbf{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.

${\mathbf{info}}=-i$
If ${\mathbf{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  ${\mathbf{info}}>0$
The algorithm failed to compute an eigenvalue while working on the submatrix lying in rows and columns ${\mathbf{info}}/\left({\mathbf{n}}+1\right)$ through .

## Accuracy

The computed eigenvalues and eigenvectors are exact for a nearby matrix $\left(T+E\right)$, where
 $E2 = Oε T2 ,$
and $\epsilon$ is the machine precision.
If ${\lambda }_{i}$ is an exact eigenvalue and ${\stackrel{~}{\lambda }}_{i}$ is the corresponding computed value, then
 $λ~i - λi ≤ c n ε T2 ,$
where $c\left(n\right)$ is a modestly increasing function of $n$.
If ${z}_{i}$ is the corresponding exact eigenvector, and ${\stackrel{~}{z}}_{i}$ is the corresponding computed eigenvector, then the angle $\theta \left({\stackrel{~}{z}}_{i},{z}_{i}\right)$ between them is bounded as follows:
 $θ z~i,zi ≤ cnεT2 mini≠jλ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).

If only eigenvalues are required, the total number of floating-point operations is approximately proportional to ${n}^{2}$. 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

```