F08 Chapter Contents
F08 Chapter Introduction
NAG Library Manual

NAG Library Routine DocumentF08JEF (DSTEQR)

Note:  before using this routine, please read the Users' Note for your implementation to check the interpretation of bold italicised terms and other implementation-dependent details.

1  Purpose

F08JEF (DSTEQR) computes all the eigenvalues and, optionally, all the eigenvectors of a real symmetric tridiagonal matrix, or of a real symmetric matrix which has been reduced to tridiagonal form.

2  Specification

 SUBROUTINE F08JEF ( COMPZ, N, D, E, Z, LDZ, WORK, INFO)
 INTEGER N, LDZ, INFO REAL (KIND=nag_wp) D(*), E(*), Z(LDZ,*), WORK(*) CHARACTER(1) COMPZ
The routine may be called by its LAPACK name dsteqr.

3  Description

F08JEF (DSTEQR) computes all the eigenvalues and, optionally, all the eigenvectors of a real symmetric tridiagonal matrix $T$. In other words, it can compute the spectral factorization of $T$ as
 $T=ZΛZT,$
where $\Lambda$ is a diagonal matrix whose diagonal elements are the eigenvalues ${\lambda }_{i}$, and $Z$ is the orthogonal matrix whose columns are the eigenvectors ${z}_{i}$. Thus
 $Tzi=λizi, i=1,2,…,n.$
The routine may also be used to compute all the eigenvalues and eigenvectors of a real symmetric matrix $A$ which has been reduced to tridiagonal form $T$:
 $A =QTQT, where ​Q​ is orthogonal =QZΛQZT.$
In this case, the matrix $Q$ must be formed explicitly and passed to F08JEF (DSTEQR), which must be called with ${\mathbf{COMPZ}}=\text{'V'}$. The routines which must be called to perform the reduction to tridiagonal form and form $Q$ are:
 full matrix F08FEF (DSYTRD) and F08FFF (DORGTR) full matrix, packed storage F08GEF (DSPTRD) and F08GFF (DOPGTR) band matrix F08HEF (DSBTRD) with ${\mathbf{VECT}}=\text{'V'}$.
F08JEF (DSTEQR) uses the implicitly shifted $QR$ algorithm, switching between the $QR$ and $QL$ variants in order to handle graded matrices effectively (see Greenbaum and Dongarra (1980)). The eigenvectors are normalized so that ${‖{z}_{i}‖}_{2}=1$, but are determined only to within a factor $±1$.
If only the eigenvalues of $T$ are required, it is more efficient to call F08JFF (DSTERF) instead. If $T$ is positive definite, small eigenvalues can be computed more accurately by F08JGF (DPTEQR).

4  References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore
Greenbaum A and Dongarra J J (1980) Experiments with QR/QL methods for the symmetric triangular eigenproblem LAPACK Working Note No. 17 (Technical Report CS-89-92) University of Tennessee, Knoxville
Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia

5  Parameters

1:     COMPZ – CHARACTER(1)Input
On entry: 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{'I'}$
The eigenvalues and eigenvectors of $T$ are computed (and the array Z is initialized by the routine).
${\mathbf{COMPZ}}=\text{'V'}$
The eigenvalues and eigenvectors of $A$ are computed (and the array Z must contain the matrix $Q$ on entry).
Constraint: ${\mathbf{COMPZ}}=\text{'N'}$, $\text{'V'}$ or $\text{'I'}$.
2:     N – INTEGERInput
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{N}}\ge 0$.
3:     D($*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the dimension of the array D must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$.
On entry: the diagonal elements of the tridiagonal matrix $T$.
On exit: the $n$ eigenvalues in ascending order, unless ${\mathbf{INFO}}>{\mathbf{0}}$ (in which case see Section 6).
4:     E($*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the dimension of the array E must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}-1\right)$.
On entry: the off-diagonal elements of the tridiagonal matrix $T$.
On exit: E is overwritten.
5:     Z(LDZ,$*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: 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$ if ${\mathbf{COMPZ}}=\text{'N'}$.
On entry: if ${\mathbf{COMPZ}}=\text{'V'}$, Z must contain the orthogonal matrix $Q$ from the reduction to tridiagonal form.
If ${\mathbf{COMPZ}}=\text{'I'}$, Z need not be set.
On exit: if ${\mathbf{COMPZ}}=\text{'I'}$ or $\text{'V'}$, the $n$ required orthonormal eigenvectors stored as columns of $Z$; the $i$th column corresponds to the $i$th eigenvalue, where $i=1,2,\dots ,n$, unless ${\mathbf{INFO}}>{\mathbf{0}}$.
If ${\mathbf{COMPZ}}=\text{'N'}$, Z is not referenced.
6:     LDZ – INTEGERInput
On entry: the first dimension of the array Z as declared in the (sub)program from which F08JEF (DSTEQR) is called.
Constraints:
• if ${\mathbf{COMPZ}}=\text{'I'}$ or $\text{'V'}$, ${\mathbf{LDZ}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$;
• if ${\mathbf{COMPZ}}=\text{'N'}$, ${\mathbf{LDZ}}\ge 1$.
7:     WORK($*$) – REAL (KIND=nag_wp) arrayWorkspace
Note: the dimension of the array WORK must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,2×\left({\mathbf{N}}-1\right)\right)$ if ${\mathbf{COMPZ}}=\text{'V'}$ or $\text{'I'}$ and at least $1$ if ${\mathbf{COMPZ}}=\text{'N'}$.
If ${\mathbf{COMPZ}}=\text{'N'}$, WORK is not referenced.
8:     INFO – INTEGEROutput
On exit: ${\mathbf{INFO}}=0$ unless the routine detects an error (see Section 6).

6  Error Indicators and Warnings

Errors or warnings detected by the routine:
${\mathbf{INFO}}<0$
If ${\mathbf{INFO}}=-i$, argument $i$ had an illegal value. An explanatory message is output, and execution of the program is terminated.
${\mathbf{INFO}}>0$
The algorithm has failed to find all the eigenvalues after a total of $30×{\mathbf{N}}$ iterations. In this case, D and E contain on exit the diagonal and off-diagonal elements, respectively, of a tridiagonal matrix similar to $T$. If ${\mathbf{INFO}}=i$, then $i$ off-diagonal elements have not converged to zero.

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

The total number of floating point operations is typically about $24{n}^{2}$ if ${\mathbf{COMPZ}}=\text{'N'}$ and about $7{n}^{3}$ if ${\mathbf{COMPZ}}=\text{'V'}$ or $\text{'I'}$, but depends on how rapidly the algorithm converges. When ${\mathbf{COMPZ}}=\text{'N'}$, the operations are all performed in scalar mode; the additional operations to compute the eigenvectors when ${\mathbf{COMPZ}}=\text{'V'}$ or $\text{'I'}$ can be vectorized and on some machines may be performed much faster.
The complex analogue of this routine is F08JSF (ZSTEQR).

9  Example

This example computes all the eigenvalues and eigenvectors of the symmetric tridiagonal matrix $T$, where
 $T = -6.99 -0.44 0.00 0.00 -0.44 7.92 -2.63 0.00 0.00 -2.63 2.34 -1.18 0.00 0.00 -1.18 0.32 .$
See also the examples for F08FFF (DORGTR), F08GFF (DOPGTR) or F08HEF (DSBTRD), which illustrate the use of this routine to compute the eigenvalues and eigenvectors of a full or band symmetric matrix.

9.1  Program Text

Program Text (f08jefe.f90)

9.2  Program Data

Program Data (f08jefe.d)

9.3  Program Results

Program Results (f08jefe.r)