# NAG FL Interfacef08jsf (zsteqr)

## ▸▿ Contents

Settings help

FL Name Style:

FL Specification Language:

## 1Purpose

f08jsf computes all the eigenvalues and, optionally, all the eigenvectors of a complex Hermitian matrix which has been reduced to tridiagonal form.

## 2Specification

Fortran Interface
 Subroutine f08jsf ( n, d, e, z, ldz, work, info)
 Integer, Intent (In) :: n, ldz Integer, Intent (Out) :: info Real (Kind=nag_wp), Intent (Inout) :: d(*), e(*), work(*) Complex (Kind=nag_wp), Intent (Inout) :: z(ldz,*) Character (1), Intent (In) :: compz
#include <nag.h>
 void f08jsf_ (const char *compz, const Integer *n, double d[], double e[], Complex z[], const Integer *ldz, double work[], Integer *info, const Charlen length_compz)
The routine may be called by the names f08jsf, nagf_lapackeig_zsteqr or its LAPACK name zsteqr.

## 3Description

f08jsf 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 stores the real orthogonal matrix $Z$ in a complex array, so that it may also be used to compute all the eigenvalues and eigenvectors of a complex Hermitian matrix $A$ which has been reduced to tridiagonal form $T$:
 $A =QTQH, where ​Q​ is unitary =(QZ)Λ(QZ)H.$
In this case, the matrix $Q$ must be formed explicitly and passed to f08jsf, 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 f08fsf and f08ftf full matrix, packed storage f08gsf and f08gtf band matrix f08hsf with ${\mathbf{vect}}=\text{'V'}$.
f08jsf 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 complex factor of absolute value $1$.
If only the eigenvalues of $T$ are required, it is more efficient to call f08jff instead. If $T$ is positive definite, small eigenvalues can be computed more accurately by f08juf.

## 4References

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 https://www.netlib.org/lapack/lawnspdf/lawn17.pdf
Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia

## 5Arguments

1: $\mathbf{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{'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 routine).
Constraint: ${\mathbf{compz}}=\text{'N'}$, $\text{'V'}$ or $\text{'I'}$.
2: $\mathbf{n}$Integer Input
On entry: $n$, the order of the matrix $T$.
Constraint: ${\mathbf{n}}\ge 0$.
3: $\mathbf{d}\left(*\right)$Real (Kind=nag_wp) array Input/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: $\mathbf{e}\left(*\right)$Real (Kind=nag_wp) array Input/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: $\mathbf{z}\left({\mathbf{ldz}},*\right)$Complex (Kind=nag_wp) array Input/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 unitary matrix $Q$ from the reduction to tridiagonal form.
If ${\mathbf{compz}}=\text{'I'}$, z need not be set.
On exit: if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, 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: $\mathbf{ldz}$Integer Input
On entry: the first dimension of the array z as declared in the (sub)program from which f08jsf is called.
Constraints:
• if ${\mathbf{compz}}=\text{'V'}$ or $\text{'I'}$, ${\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: $\mathbf{work}\left(*\right)$Real (Kind=nag_wp) array Workspace
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: $\mathbf{info}$Integer Output
On exit: ${\mathbf{info}}=0$ unless the routine detects an error (see Section 6).

## 6Error Indicators and Warnings

${\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 unitarily similar to $T$. $⟨\mathit{\text{value}}⟩$ off-diagonal elements have not converged to zero.

## 7Accuracy

The computed eigenvalues and eigenvectors are exact for a nearby matrix $\left(T+E\right)$, where
 $‖E‖2 = O(ε) ‖T‖2 ,$
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) ε ‖T‖2 ,$
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) ≤ c(n)ε‖T‖2 mini≠j|λi-λj| .$
Thus the accuracy of a computed eigenvector depends on the gap between its eigenvalue and all the other eigenvalues.

## 8Parallelism and Performance

The total number of real floating-point operations is typically about $24{n}^{2}$ if ${\mathbf{compz}}=\text{'N'}$ and about $14{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.