f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_dstebz (f08jjc)

## 1  Purpose

nag_dstebz (f08jjc) computes some (or all) of the eigenvalues of a real symmetric tridiagonal matrix, by bisection.

## 2  Specification

 #include #include
 void nag_dstebz (Nag_RangeType range, Nag_EigValRankType rank, Integer n, double vl, double vu, Integer il, Integer iu, double abstol, const double d[], const double e[], Integer *m, Integer *nsplit, double w[], Integer iblock[], Integer isplit[], NagError *fail)

## 3  Description

nag_dstebz (f08jjc) uses bisection to compute some or all of the eigenvalues of a real symmetric tridiagonal matrix $T$.
It searches for zero or negligible off-diagonal elements of $T$ to see if the matrix splits into block diagonal form:
 $T = T1 T2 . . . Tp .$
It performs bisection on each of the blocks ${T}_{i}$ and returns the block index of each computed eigenvalue, so that a subsequent call to nag_dstein (f08jkc) to compute eigenvectors can also take advantage of the block structure.
Kahan W (1966) Accurate eigenvalues of a symmetric tridiagonal matrix Report CS41 Stanford University

## 5  Arguments

1:     rangeNag_RangeTypeInput
On entry: indicates which eigenvalues are required.
${\mathbf{range}}=\mathrm{Nag_AllValues}$
All the eigenvalues are required.
${\mathbf{range}}=\mathrm{Nag_Interval}$
All the eigenvalues in the half-open interval (vl,vu] are required.
${\mathbf{range}}=\mathrm{Nag_Indices}$
Eigenvalues with indices il to iu are required.
Constraint: ${\mathbf{range}}=\mathrm{Nag_AllValues}$, $\mathrm{Nag_Interval}$ or $\mathrm{Nag_Indices}$.
2:     rankNag_EigValRankTypeInput
On entry: indicates the order in which the eigenvalues and their block numbers are to be stored.
${\mathbf{rank}}=\mathrm{Nag_ByBlock}$
The eigenvalues are to be grouped by split-off block and ordered from smallest to largest within each block.
${\mathbf{rank}}=\mathrm{Nag_Entire}$
The eigenvalues for the entire matrix are to be ordered from smallest to largest.
Constraint: ${\mathbf{rank}}=\mathrm{Nag_ByBlock}$ or $\mathrm{Nag_Entire}$.
3:     nIntegerInput
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$.
4:     vldoubleInput
5:     vudoubleInput
On entry: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, the lower and upper bounds, respectively, of the half-open interval (vl,vu] within which the required eigenvalues lie.
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Indices}$, vl is not referenced.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, ${\mathbf{vl}}<{\mathbf{vu}}$.
6:     ilIntegerInput
7:     iuIntegerInput
On entry: if ${\mathbf{range}}=\mathrm{Nag_Indices}$, the indices of the first and last eigenvalues, respectively, to be computed (assuming that the eigenvalues are in ascending order).
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Interval}$, il is not referenced.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Indices}$, $1\le {\mathbf{il}}\le {\mathbf{iu}}\le {\mathbf{n}}$.
8:     abstoldoubleInput
On entry: the absolute tolerance to which each eigenvalue is required. An eigenvalue (or cluster) is considered to have converged if it lies in an interval of width $\text{}\le {\mathbf{abstol}}$. If ${\mathbf{abstol}}\le 0.0$, then the tolerance is taken as .
9:     d[$\mathit{dim}$]const doubleInput
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$.
10:   e[$\mathit{dim}$]const doubleInput
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$.
11:   mInteger *Output
On exit: $m$, the actual number of eigenvalues found.
12:   nsplitInteger *Output
On exit: the number of diagonal blocks which constitute the tridiagonal matrix $T$.
13:   w[n]doubleOutput
On exit: the required eigenvalues of the tridiagonal matrix $T$ stored in ${\mathbf{w}}\left[0\right]$ to ${\mathbf{w}}\left[m-1\right]$.
14:   iblock[n]IntegerOutput
On exit: at each row/column $j$ where ${\mathbf{e}}\left[j-1\right]$ is zero or negligible, $T$ is considered to split into a block diagonal matrix and ${\mathbf{iblock}}\left[\mathit{i}-1\right]$ contains the block number of the eigenvalue stored in ${\mathbf{w}}\left[\mathit{i}-1\right]$, for $\mathit{i}=1,2,\dots ,m$. Note that ${\mathbf{iblock}}\left[\mathit{i}-1\right]<0$ for some $i$ whenever ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_CONVERGENCE (see Section 6) and ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Interval}$.
15:   isplit[n]IntegerOutput
On exit: the leading nsplit elements contain the points at which $T$ splits up into sub-matrices as follows. The first sub-matrix consists of rows/columns $1$ to ${\mathbf{isplit}}\left[0\right]$, the second sub-matrix consists of rows/columns ${\mathbf{isplit}}\left[0\right]+1$ to ${\mathbf{isplit}}\left[1\right]$, $\dots$, and the nsplit(th) sub-matrix consists of rows/columns ${\mathbf{isplit}}\left[{\mathbf{nsplit}}-2\right]+1$ to ${\mathbf{isplit}}\left[{\mathbf{nsplit}}-1\right]$ ($\text{}=n$).
16:   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
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Interval}$, the algorithm failed to compute some (or all) of the required eigenvalues to the required accuracy. More precisely, ${\mathbf{iblock}}\left[⟨\mathit{\text{value}}⟩\right]<0$ indicates that eigenvalue $⟨\mathit{\text{value}}⟩$ (stored in ${\mathbf{w}}\left[⟨\mathit{\text{value}}⟩\right]$) failed to converge.
If ${\mathbf{range}}=\mathrm{Nag_Indices}$, the algorithm failed to compute some (or all) of the required eigenvalues. Try calling the function again with ${\mathbf{range}}=\mathrm{Nag_AllValues}$.
If ${\mathbf{range}}=\mathrm{Nag_Indices}$, the algorithm failed to compute some (or all) of the required eigenvalues. Try calling the function again with ${\mathbf{range}}=\mathrm{Nag_AllValues}$. If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Interval}$, the algorithm failed to compute some (or all) of the required eigenvalues to the required accuracy. More precisely, ${\mathbf{iblock}}\left[⟨\mathit{\text{value}}⟩\right]<0$ indicates that eigenvalue $⟨\mathit{\text{value}}⟩$ (stored in ${\mathbf{w}}\left[⟨\mathit{\text{value}}⟩\right]$) failed to converge.
No eigenvalues have been computed. The floating-point arithmetic on the computer is not behaving as expected.
NE_ENUM_INT_3
On entry, ${\mathbf{range}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{il}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{iu}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Indices}$, $1\le {\mathbf{il}}\le {\mathbf{iu}}\le {\mathbf{n}}$.
NE_ENUM_REAL_2
On entry, ${\mathbf{range}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{vl}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{vu}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, ${\mathbf{vl}}<{\mathbf{vu}}$.
NE_INT
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 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 eigenvalues of $T$ are computed to high relative accuracy which means that if they vary widely in magnitude, then any small eigenvalues will be computed more accurately than, for example, with the standard $QR$ method. However, the reduction to tridiagonal form (prior to calling the function) may exclude the possibility of obtaining high relative accuracy in the small eigenvalues of the original matrix if its eigenvalues vary widely in magnitude.

## 8  Parallelism and Performance

nag_dstebz (f08jjc) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.