F08 Chapter Contents
F08 Chapter Introduction
NAG Library Manual

# NAG Library Routine DocumentF08HEF (DSBTRD)

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

F08HEF (DSBTRD) reduces a real symmetric band matrix to tridiagonal form.

## 2  Specification

 SUBROUTINE F08HEF ( VECT, UPLO, N, KD, AB, LDAB, D, E, Q, LDQ, WORK, INFO)
 INTEGER N, KD, LDAB, LDQ, INFO REAL (KIND=nag_wp) AB(LDAB,*), D(N), E(N-1), Q(LDQ,*), WORK(N) CHARACTER(1) VECT, UPLO
The routine may be called by its LAPACK name dsbtrd.

## 3  Description

F08HEF (DSBTRD) reduces a symmetric band matrix $A$ to symmetric tridiagonal form $T$ by an orthogonal similarity transformation:
 $T = QT A Q .$
The orthogonal matrix $Q$ is determined as a product of Givens rotation matrices, and may be formed explicitly by the routine if required.
The routine uses a vectorizable form of the reduction, due to Kaufman (1984).

## 4  References

Kaufman L (1984) Banded eigenvalue solvers on vector machines ACM Trans. Math. Software 10 73–86
Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia

## 5  Parameters

1:     VECT – CHARACTER(1)Input
On entry: indicates whether $Q$ is to be returned.
${\mathbf{VECT}}=\text{'V'}$
$Q$ is returned.
${\mathbf{VECT}}=\text{'U'}$
$Q$ is updated (and the array Q must contain a matrix on entry).
${\mathbf{VECT}}=\text{'N'}$
$Q$ is not required.
Constraint: ${\mathbf{VECT}}=\text{'V'}$, $\text{'U'}$ or $\text{'N'}$.
2:     UPLO – CHARACTER(1)Input
On entry: indicates whether the upper or lower triangular part of $A$ is stored.
${\mathbf{UPLO}}=\text{'U'}$
The upper triangular part of $A$ is stored.
${\mathbf{UPLO}}=\text{'L'}$
The lower triangular part of $A$ is stored.
Constraint: ${\mathbf{UPLO}}=\text{'U'}$ or $\text{'L'}$.
3:     N – INTEGERInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{N}}\ge 0$.
4:     KD – INTEGERInput
On entry: if ${\mathbf{UPLO}}=\text{'U'}$, the number of superdiagonals, ${k}_{d}$, of the matrix $A$.
If ${\mathbf{UPLO}}=\text{'L'}$, the number of subdiagonals, ${k}_{d}$, of the matrix $A$.
Constraint: ${\mathbf{KD}}\ge 0$.
5:     AB(LDAB,$*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the second dimension of the array AB must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$.
On entry: the upper or lower triangle of the $n$ by $n$ symmetric band matrix $A$.
The matrix is stored in rows $1$ to ${k}_{d}+1$, more precisely,
• if ${\mathbf{UPLO}}=\text{'U'}$, the elements of the upper triangle of $A$ within the band must be stored with element ${A}_{ij}$ in ${\mathbf{AB}}\left({k}_{d}+1+i-j,j\right)\text{​ for ​}\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,j-{k}_{d}\right)\le i\le j$;
• if ${\mathbf{UPLO}}=\text{'L'}$, the elements of the lower triangle of $A$ within the band must be stored with element ${A}_{ij}$ in ${\mathbf{AB}}\left(1+i-j,j\right)\text{​ for ​}j\le i\le \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(n,j+{k}_{d}\right)\text{.}$
On exit: AB is overwritten by values generated during the reduction to tridiagonal form.
The first superdiagonal or subdiagonal and the diagonal of the tridiagonal matrix $T$ are returned in AB using the same storage format as described above.
6:     LDAB – INTEGERInput
On entry: the first dimension of the array AB as declared in the (sub)program from which F08HEF (DSBTRD) is called.
Constraint: ${\mathbf{LDAB}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{KD}}+1\right)$.
7:     D(N) – REAL (KIND=nag_wp) arrayOutput
On exit: the diagonal elements of the tridiagonal matrix $T$.
8:     E(${\mathbf{N}}-1$) – REAL (KIND=nag_wp) arrayOutput
On exit: the off-diagonal elements of the tridiagonal matrix $T$.
9:     Q(LDQ,$*$) – REAL (KIND=nag_wp) arrayInput/Output
Note: the second dimension of the array Q must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$ if ${\mathbf{VECT}}=\text{'V'}$ or $\text{'U'}$ and at least $1$ if ${\mathbf{VECT}}=\text{'N'}$.
On entry: if ${\mathbf{VECT}}=\text{'U'}$, Q must contain the matrix formed in a previous stage of the reduction (for example, the reduction of a banded symmetric-definite generalized eigenproblem); otherwise Q need not be set.
On exit: if ${\mathbf{VECT}}=\text{'V'}$ or $\text{'U'}$, the $n$ by $n$ matrix $Q$.
If ${\mathbf{VECT}}=\text{'N'}$, Q is not referenced.
10:   LDQ – INTEGERInput
On entry: the first dimension of the array Q as declared in the (sub)program from which F08HEF (DSBTRD) is called.
Constraints:
• if ${\mathbf{VECT}}=\text{'V'}$ or $\text{'U'}$, ${\mathbf{LDQ}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{N}}\right)$;
• if ${\mathbf{VECT}}=\text{'N'}$, ${\mathbf{LDQ}}\ge 1$.
11:   WORK(N) – REAL (KIND=nag_wp) arrayWorkspace
12:   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.

## 7  Accuracy

The computed tridiagonal matrix $T$ is exactly similar to a nearby matrix $\left(A+E\right)$, where
 $E2≤ c n ε A2 ,$
$c\left(n\right)$ is a modestly increasing function of $n$, and $\epsilon$ is the machine precision.
The elements of $T$ themselves may be sensitive to small perturbations in $A$ or to rounding errors in the computation, but this does not affect the stability of the eigenvalues and eigenvectors.
The computed matrix $Q$ differs from an exactly orthogonal matrix by a matrix $E$ such that
 $E2 = Oε ,$
where $\epsilon$ is the machine precision.

The total number of floating point operations is approximately $6{n}^{2}k$ if ${\mathbf{VECT}}=\text{'N'}$ with $3{n}^{3}\left(k-1\right)/k$ additional operations if ${\mathbf{VECT}}=\text{'V'}$.
The complex analogue of this routine is F08HSF (ZHBTRD).

## 9  Example

This example computes all the eigenvalues and eigenvectors of the matrix $A$, where
 $A = 4.99 0.04 0.22 0.00 0.04 1.05 -0.79 1.04 0.22 -0.79 -2.31 -1.30 0.00 1.04 -1.30 -0.43 .$
Here $A$ is symmetric and is treated as a band matrix. The program first calls F08HEF (DSBTRD) to reduce $A$ to tridiagonal form $T$, and to form the orthogonal matrix $Q$; the results are then passed to F08JEF (DSTEQR) which computes the eigenvalues and eigenvectors of $A$.

### 9.1  Program Text

Program Text (f08hefe.f90)

### 9.2  Program Data

Program Data (f08hefe.d)

### 9.3  Program Results

Program Results (f08hefe.r)