NAG FL Interfacef08jjf (dstebz)

▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

1Purpose

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

2Specification

Fortran Interface
 Subroutine f08jjf ( n, vl, vu, il, iu, d, e, m, w, work, info)
 Integer, Intent (In) :: n, il, iu Integer, Intent (Out) :: m, nsplit, iblock(n), isplit(n), iwork(3*n), info Real (Kind=nag_wp), Intent (In) :: vl, vu, abstol, d(*), e(*) Real (Kind=nag_wp), Intent (Out) :: w(n), work(4*n) Character (1), Intent (In) :: range, order
#include <nag.h>
 void f08jjf_ (const char *range, const char *order, const Integer *n, const double *vl, const double *vu, const Integer *il, const Integer *iu, const double *abstol, const double d[], const double e[], Integer *m, Integer *nsplit, double w[], Integer iblock[], Integer isplit[], double work[], Integer iwork[], Integer *info, const Charlen length_range, const Charlen length_order)
The routine may be called by the names f08jjf, nagf_lapackeig_dstebz or its LAPACK name dstebz.

3Description

f08jjf 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 f08jkf to compute eigenvectors can also take advantage of the block structure.

4References

Kahan W (1966) Accurate eigenvalues of a symmetric tridiagonal matrix Report CS41 Stanford University

5Arguments

1: $\mathbf{range}$Character(1) Input
On entry: indicates which eigenvalues are required.
${\mathbf{range}}=\text{'A'}$
All the eigenvalues are required.
${\mathbf{range}}=\text{'V'}$
All the eigenvalues in the half-open interval (vl,vu] are required.
${\mathbf{range}}=\text{'I'}$
Eigenvalues with indices il to iu are required.
Constraint: ${\mathbf{range}}=\text{'A'}$, $\text{'V'}$ or $\text{'I'}$.
2: $\mathbf{order}$Character(1) Input
On entry: indicates the order in which the eigenvalues and their block numbers are to be stored.
${\mathbf{order}}=\text{'B'}$
The eigenvalues are to be grouped by split-off block and ordered from smallest to largest within each block.
${\mathbf{order}}=\text{'E'}$
The eigenvalues for the entire matrix are to be ordered from smallest to largest.
Constraint: ${\mathbf{order}}=\text{'B'}$ or $\text{'E'}$.
3: $\mathbf{n}$Integer Input
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$.
4: $\mathbf{vl}$Real (Kind=nag_wp) Input
5: $\mathbf{vu}$Real (Kind=nag_wp) Input
On entry: if ${\mathbf{range}}=\text{'V'}$, the lower and upper bounds, respectively, of the half-open interval
$\left({\mathbf{vl}},{\mathbf{vu}}\right]$ within which the required eigenvalues lie.
If ${\mathbf{range}}=\text{'A'}$ or $\text{'I'}$, vl is not referenced.
Constraint: if ${\mathbf{range}}=\text{'V'}$, ${\mathbf{vl}}<{\mathbf{vu}}$.
6: $\mathbf{il}$Integer Input
7: $\mathbf{iu}$Integer Input
On entry: if ${\mathbf{range}}=\text{'I'}$, the indices of the first and last eigenvalues, respectively, to be computed (assuming that the eigenvalues are in ascending order).
If ${\mathbf{range}}=\text{'A'}$ or $\text{'V'}$, il is not referenced.
Constraint: if ${\mathbf{range}}=\text{'I'}$, $1\le {\mathbf{il}}\le {\mathbf{iu}}\le {\mathbf{n}}$.
8: $\mathbf{abstol}$Real (Kind=nag_wp) Input
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$, the tolerance is taken as .
9: $\mathbf{d}\left(*\right)$Real (Kind=nag_wp) array Input
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$.
10: $\mathbf{e}\left(*\right)$Real (Kind=nag_wp) array Input
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$.
11: $\mathbf{m}$Integer Output
On exit: $m$, the actual number of eigenvalues found.
12: $\mathbf{nsplit}$Integer Output
On exit: the number of diagonal blocks which constitute the tridiagonal matrix $T$.
13: $\mathbf{w}\left({\mathbf{n}}\right)$Real (Kind=nag_wp) array Output
On exit: the required eigenvalues of the tridiagonal matrix $T$ stored in ${\mathbf{w}}\left(1\right)$ to ${\mathbf{w}}\left(m\right)$.
14: $\mathbf{iblock}\left({\mathbf{n}}\right)$Integer array Output
On exit: at each row/column $j$ where ${\mathbf{e}}\left(j\right)$ is zero or negligible, $T$ is considered to split into a block diagonal matrix and ${\mathbf{iblock}}\left(\mathit{i}\right)$ contains the block number of the eigenvalue stored in ${\mathbf{w}}\left(\mathit{i}\right)$, for $\mathit{i}=1,2,\dots ,m$. Note that ${\mathbf{iblock}}\left(\mathit{i}\right)<0$ for some $i$ whenever ${\mathbf{info}}={\mathbf{1}}$ or ${\mathbf{3}}$ (see Section 6) and ${\mathbf{range}}=\text{'A'}$ or $\text{'V'}$.
15: $\mathbf{isplit}\left({\mathbf{n}}\right)$Integer array Output
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(1\right)$, the second sub-matrix consists of rows/columns ${\mathbf{isplit}}\left(1\right)+1$ to ${\mathbf{isplit}}\left(2\right)$, $\dots$, and the nsplit(th) sub-matrix consists of rows/columns ${\mathbf{isplit}}\left({\mathbf{nsplit}}-1\right)+1$ to ${\mathbf{isplit}}\left({\mathbf{nsplit}}\right)$ ($\text{}=n$).
16: $\mathbf{work}\left(4×{\mathbf{n}}\right)$Real (Kind=nag_wp) array Workspace
17: $\mathbf{iwork}\left(3×{\mathbf{n}}\right)$Integer array Workspace
18: $\mathbf{info}$Integer Output
On exit: ${\mathbf{info}}=0$ unless the routine detects an error (see Section 6).

6Error Indicators and Warnings

If failures with ${\mathbf{info}}\ge 1$ are causing persistent trouble and you have checked that the routine is being called correctly, please contact NAG.
${\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}}=1$
If ${\mathbf{range}}=\text{'A'}$ or $\text{'V'}$, 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.
${\mathbf{info}}=2$
If ${\mathbf{range}}=\text{'I'}$, the algorithm failed to compute some (or all) of the required eigenvalues. Try calling the routine again with ${\mathbf{range}}=\text{'A'}$.
${\mathbf{info}}=3$
If ${\mathbf{range}}=\text{'I'}$, see the description above for ${\mathbf{info}}=2$.
If ${\mathbf{range}}=\text{'A'}$ or $\text{'V'}$, see the description above for ${\mathbf{info}}=1$.
${\mathbf{info}}=4$
No eigenvalues have been computed. The floating-point arithmetic on the computer is not behaving as expected.

7Accuracy

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 routine) may exclude the possibility of obtaining high relative accuracy in the small eigenvalues of the original matrix if its eigenvalues vary widely in magnitude.

8Parallelism and Performance

f08jjf is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this routine. Please also consult the Users' Note for your implementation for any additional implementation-specific information.