f08 Chapter Contents
f08 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_dsteqr (f08jec)

## 1  Purpose

nag_dsteqr (f08jec) 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

 #include #include
 void nag_dsteqr (Nag_OrderType order, Nag_ComputeZType compz, Integer n, double d[], double e[], double z[], Integer pdz, NagError *fail)

## 3  Description

nag_dsteqr (f08jec) 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 function 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 nag_dsteqr (f08jec), which must be called with ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$. The functions which must be called to perform the reduction to tridiagonal form and form $Q$ are:
 full matrix nag_dsytrd (f08fec) and nag_dorgtr (f08ffc) full matrix, packed storage nag_dsptrd (f08gec) and nag_dopgtr (f08gfc) band matrix nag_dsbtrd (f08hec) with ${\mathbf{vect}}=\mathrm{Nag_FormQ}$.
nag_dsteqr (f08jec) 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 nag_dsterf (f08jfc) instead. If $T$ is positive definite, small eigenvalues can be computed more accurately by nag_dpteqr (f08jgc).

## 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  Arguments

1:     orderNag_OrderTypeInput
On entry: the order argument specifies the two-dimensional storage scheme being used, i.e., row-major ordering or column-major ordering. C language defined storage is specified by ${\mathbf{order}}=\mathrm{Nag_RowMajor}$. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.
Constraint: ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ or Nag_ColMajor.
2:     compzNag_ComputeZTypeInput
On entry: indicates whether the eigenvectors are to be computed.
${\mathbf{compz}}=\mathrm{Nag_NotZ}$
Only the eigenvalues are computed (and the array z is not referenced).
${\mathbf{compz}}=\mathrm{Nag_InitZ}$
The eigenvalues and eigenvectors of $T$ are computed (and the array z is initialized by the function).
${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$
The eigenvalues and eigenvectors of $A$ are computed (and the array z must contain the matrix $Q$ on entry).
Constraint: ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, $\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$.
3:     nIntegerInput
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$.
4:     d[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, 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 NE_CONVERGENCE (in which case see Section 6).
5:     e[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, 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.
6:     z[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array z must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdz}}×{\mathbf{n}}\right)$ when ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or Nag_InitZ.
The $\left(i,j\right)$th element of the matrix $Z$ is stored in
• ${\mathbf{z}}\left[\left(j-1\right)×{\mathbf{pdz}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{z}}\left[\left(i-1\right)×{\mathbf{pdz}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On entry: if ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$, z must contain the orthogonal matrix $Q$ from the reduction to tridiagonal form. If ${\mathbf{compz}}=\mathrm{Nag_InitZ}$, z must be allocated, but its contents need not be set. If ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, z is not referenced and may be a null pointer, i.e., (double *) 0.
On exit: if ${\mathbf{compz}}=\mathrm{Nag_InitZ}$ or $\mathrm{Nag_UpdateZ}$, 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{fail}}\mathbf{.}\mathbf{errnum}>0$.
z is not changed if ${\mathbf{compz}}=\mathrm{Nag_NotZ}$.
7:     pdzIntegerInput
On entry: when z is a null pointer then pdz should be set to $0$.
Constraints:
• if ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, ${\mathbf{pdz}}\ge 0$;
• if ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
8:     failNagError *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.
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_CONVERGENCE
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$. $〈\mathit{\text{value}}〉$ off-diagonal elements have not converged to zero.
NE_ENUM_INT_2
On entry, ${\mathbf{compz}}=〈\mathit{\text{value}}〉$, ${\mathbf{n}}=〈\mathit{\text{value}}〉$ and ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, ${\mathbf{pdz}}\ge 0$;
if ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
On entry, ${\mathbf{compz}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{compz}}=\mathrm{Nag_InitZ}$ or $\mathrm{Nag_UpdateZ}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
if ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, ${\mathbf{pdz}}\ge 1$.
On entry, ${\mathbf{compz}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
if ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, ${\mathbf{pdz}}\ge 1$.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdz}}>0$.
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.

## 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}}=\mathrm{Nag_NotZ}$ and about $7{n}^{3}$ if ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$, but depends on how rapidly the algorithm converges. When ${\mathbf{compz}}=\mathrm{Nag_NotZ}$, the operations are all performed in scalar mode; the additional operations to compute the eigenvectors when ${\mathbf{compz}}=\mathrm{Nag_UpdateZ}$ or $\mathrm{Nag_InitZ}$ can be vectorized and on some machines may be performed much faster.
The complex analogue of this function is nag_zsteqr (f08jsc).

## 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 nag_dorgtr (f08ffc), nag_dopgtr (f08gfc) or nag_dsbtrd (f08hec), which illustrate the use of this function to compute the eigenvalues and eigenvectors of a full or band symmetric matrix.

### 9.1  Program Text

Program Text (f08jece.c)

### 9.2  Program Data

Program Data (f08jece.d)

### 9.3  Program Results

Program Results (f08jece.r)