f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_dsbtrd (f08hec)

## 1  Purpose

nag_dsbtrd (f08hec) reduces a real symmetric band matrix to tridiagonal form.

## 2  Specification

 #include #include
 void nag_dsbtrd (Nag_OrderType order, Nag_VectType vect, Nag_UploType uplo, Integer n, Integer kd, double ab[], Integer pdab, double d[], double e[], double q[], Integer pdq, NagError *fail)

## 3  Description

nag_dsbtrd (f08hec) 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 function if required.
The function 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  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 $\mathrm{Nag_ColMajor}$.
2:     vectNag_VectTypeInput
On entry: indicates whether $Q$ is to be returned.
${\mathbf{vect}}=\mathrm{Nag_FormQ}$
$Q$ is returned.
${\mathbf{vect}}=\mathrm{Nag_UpdateQ}$
$Q$ is updated (and the array q must contain a matrix on entry).
${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$
$Q$ is not required.
Constraint: ${\mathbf{vect}}=\mathrm{Nag_FormQ}$, $\mathrm{Nag_UpdateQ}$ or $\mathrm{Nag_DoNotForm}$.
3:     uploNag_UploTypeInput
On entry: indicates whether the upper or lower triangular part of $A$ is stored.
${\mathbf{uplo}}=\mathrm{Nag_Upper}$
The upper triangular part of $A$ is stored.
${\mathbf{uplo}}=\mathrm{Nag_Lower}$
The lower triangular part of $A$ is stored.
Constraint: ${\mathbf{uplo}}=\mathrm{Nag_Upper}$ or $\mathrm{Nag_Lower}$.
4:     nIntegerInput
On entry: $n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 0$.
5:     kdIntegerInput
On entry: if ${\mathbf{uplo}}=\mathrm{Nag_Upper}$, the number of superdiagonals, ${k}_{d}$, of the matrix $A$.
If ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, the number of subdiagonals, ${k}_{d}$, of the matrix $A$.
Constraint: ${\mathbf{kd}}\ge 0$.
6:     ab[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array ab must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdab}}×{\mathbf{n}}\right)$.
On entry: the upper or lower triangle of the $n$ by $n$ symmetric band matrix $A$.
This is stored as a notional two-dimensional array with row elements or column elements stored contiguously. The storage of elements of ${A}_{ij}$, depends on the order and uplo arguments as follows:
• if ${\mathbf{order}}=\mathrm{Nag_ColMajor}$ and ${\mathbf{uplo}}=\mathrm{Nag_Upper}$,
${A}_{ij}$ is stored in ${\mathbf{ab}}\left[{k}_{d}+i-j+\left(j-1\right)×{\mathbf{pdab}}\right]$, for $j=1,\dots ,n$ and $i=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,j-{k}_{d}\right),\dots ,j$;
• if ${\mathbf{order}}=\mathrm{Nag_ColMajor}$ and ${\mathbf{uplo}}=\mathrm{Nag_Lower}$,
${A}_{ij}$ is stored in ${\mathbf{ab}}\left[i-j+\left(j-1\right)×{\mathbf{pdab}}\right]$, for $j=1,\dots ,n$ and $i=j,\dots ,\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(n,j+{k}_{d}\right)$;
• if ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ and ${\mathbf{uplo}}=\mathrm{Nag_Upper}$,
${A}_{ij}$ is stored in ${\mathbf{ab}}\left[j-i+\left(i-1\right)×{\mathbf{pdab}}\right]$, for $i=1,\dots ,n$ and $j=i,\dots ,\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(n,i+{k}_{d}\right)$;
• if ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ and ${\mathbf{uplo}}=\mathrm{Nag_Lower}$,
${A}_{ij}$ is stored in ${\mathbf{ab}}\left[{k}_{d}+j-i+\left(i-1\right)×{\mathbf{pdab}}\right]$, for $i=1,\dots ,n$ and $j=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,i-{k}_{d}\right),\dots ,i$.
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.
7:     pdabIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) of the matrix $A$ in the array ab.
Constraint: ${\mathbf{pdab}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{kd}}+1\right)$.
8:     d[n]doubleOutput
On exit: the diagonal elements of the tridiagonal matrix $T$.
9:     e[${\mathbf{n}}-1$]doubleOutput
On exit: the off-diagonal elements of the tridiagonal matrix $T$.
10:   q[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array q must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdq}}×{\mathbf{n}}\right)$ when ${\mathbf{vect}}=\mathrm{Nag_FormQ}$ or $\mathrm{Nag_UpdateQ}$;
• $1$ when ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$.
The $\left(i,j\right)$th element of the matrix $Q$ is stored in
• ${\mathbf{q}}\left[\left(j-1\right)×{\mathbf{pdq}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{q}}\left[\left(i-1\right)×{\mathbf{pdq}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On entry: if ${\mathbf{vect}}=\mathrm{Nag_UpdateQ}$, 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}}=\mathrm{Nag_FormQ}$ or $\mathrm{Nag_UpdateQ}$, the $n$ by $n$ matrix $Q$.
If ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, q is not referenced.
11:   pdqIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array q.
Constraints:
• if ${\mathbf{vect}}=\mathrm{Nag_FormQ}$ or $\mathrm{Nag_UpdateQ}$, ${\mathbf{pdq}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• if ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, ${\mathbf{pdq}}\ge 1$.
12:   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_ENUM_INT_2
On entry, ${\mathbf{vect}}=⟨\mathit{\text{value}}⟩$, ${\mathbf{pdq}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{vect}}=\mathrm{Nag_FormQ}$ or $\mathrm{Nag_UpdateQ}$, ${\mathbf{pdq}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
if ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, ${\mathbf{pdq}}\ge 1$.
NE_INT
On entry, ${\mathbf{kd}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{kd}}\ge 0$.
On entry, ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pdab}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdab}}>0$.
On entry, ${\mathbf{pdq}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdq}}>0$.
NE_INT_2
On entry, ${\mathbf{pdab}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{kd}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdab}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{kd}}+1\right)$.
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 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.

## 8  Parallelism and Performance

nag_dsbtrd (f08hec) is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
nag_dsbtrd (f08hec) makes calls to BLAS and/or LAPACK routines, which may be threaded within the vendor library used by this implementation. Consult the documentation for the vendor library for further information.

The total number of floating-point operations is approximately $6{n}^{2}k$ if ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$ with $3{n}^{3}\left(k-1\right)/k$ additional operations if ${\mathbf{vect}}=\mathrm{Nag_FormQ}$.
The complex analogue of this function is nag_zhbtrd (f08hsc).

## 10  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 nag_dsbtrd (f08hec) to reduce $A$ to tridiagonal form $T$, and to form the orthogonal matrix $Q$; the results are then passed to nag_dsteqr (f08jec) which computes the eigenvalues and eigenvectors of $A$.

### 10.1  Program Text

Program Text (f08hece.c)

### 10.2  Program Data

Program Data (f08hece.d)

### 10.3  Program Results

Program Results (f08hece.r)