Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

# NAG Toolbox: nag_lapack_dsbtrd (f08he)

## Purpose

nag_lapack_dsbtrd (f08he) reduces a real symmetric band matrix to tridiagonal form.

## Syntax

[ab, d, e, q, info] = f08he(vect, uplo, kd, ab, q, 'n', n)
[ab, d, e, q, info] = nag_lapack_dsbtrd(vect, uplo, kd, ab, q, 'n', n)

## Description

nag_lapack_dsbtrd (f08he) 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).

## 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

## Parameters

### Compulsory Input Parameters

1:     $\mathrm{vect}$ – string (length ≥ 1)
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:     $\mathrm{uplo}$ – string (length ≥ 1)
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:     $\mathrm{kd}$int64int32nag_int scalar
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$.
4:     $\mathrm{ab}\left(\mathit{ldab},:\right)$ – double array
The first dimension of the array ab must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{kd}}+1\right)$.
The second dimension of the array ab must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
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{.}$
5:     $\mathrm{q}\left(\mathit{ldq},:\right)$ – double array
The first dimension, $\mathit{ldq}$, of the array q must satisfy
• if ${\mathbf{vect}}=\text{'V'}$ or $\text{'U'}$, $\mathit{ldq}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• if ${\mathbf{vect}}=\text{'N'}$, $\mathit{ldq}\ge 1$.
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'}$.
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.

### Optional Input Parameters

1:     $\mathrm{n}$int64int32nag_int scalar
Default: the first dimension of the array ab and the second dimension of the array ab. (An error is raised if these dimensions are not equal.)
$n$, the order of the matrix $A$.
Constraint: ${\mathbf{n}}\ge 0$.

### Output Parameters

1:     $\mathrm{ab}\left(\mathit{ldab},:\right)$ – double array
The first dimension of the array ab will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{kd}}+1\right)$.
The second dimension of the array ab will be $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
ab stores 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.
2:     $\mathrm{d}\left({\mathbf{n}}\right)$ – double array
The diagonal elements of the tridiagonal matrix $T$.
3:     $\mathrm{e}\left({\mathbf{n}}-1\right)$ – double array
The off-diagonal elements of the tridiagonal matrix $T$.
4:     $\mathrm{q}\left(\mathit{ldq},:\right)$ – double array
The first dimension, $\mathit{ldq}$, of the array q will be
• if ${\mathbf{vect}}=\text{'V'}$ or $\text{'U'}$, $\mathit{ldq}=\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• if ${\mathbf{vect}}=\text{'N'}$, $\mathit{ldq}=1$.
The second dimension of the array q will be $\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'}$.
If ${\mathbf{vect}}=\text{'V'}$ or $\text{'U'}$, the $n$ by $n$ matrix $Q$.
If ${\mathbf{vect}}=\text{'N'}$, q is not referenced.
5:     $\mathrm{info}$int64int32nag_int scalar
${\mathbf{info}}=0$ unless the function detects an error (see Error Indicators and Warnings).

## Error Indicators and Warnings

${\mathbf{info}}=-i$
If ${\mathbf{info}}=-i$, parameter $i$ had an illegal value on entry. The parameters are numbered as follows:
1: vect, 2: uplo, 3: n, 4: kd, 5: ab, 6: ldab, 7: d, 8: e, 9: q, 10: ldq, 11: work, 12: info.
It is possible that info refers to a parameter that is omitted from the MATLAB interface. This usually indicates that an error in one of the other input parameters has caused an incorrect value to be inferred.

## 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.

## Further Comments

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 function is nag_lapack_zhbtrd (f08hs).

## 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_lapack_dsbtrd (f08he) to reduce $A$ to tridiagonal form $T$, and to form the orthogonal matrix $Q$; the results are then passed to nag_lapack_dsteqr (f08je) which computes the eigenvalues and eigenvectors of $A$.
```function f08he_example

fprintf('f08he example results\n\n');

% Symmetric band matrix A, stored on symmetric banded format
uplo = 'L';
kd   = int64(2);
n    = int64(4);
ab   = [4.99,  1.05, -2.31, -0.43;
0.04, -0.79, -1.30,  0;
0.22,  1.04,  0,     0];

% Reduce A to tridiagonal form and compute Q
vect = 'V';
q = zeros(n, n);
[apf, d, e, q, info] = f08he( ...
vect, uplo, kd, ab, q);

% Calculate eigenvalues and eigenvectors of A
[w, ~, z, info] = f08je( ...
vect, d, e, 'z', q);

% Normalize eigenvectors: largest element positive
for j = 1:n
[~,k] = max(abs(z(:,j)));
if z(k,j) < 0;
z(:,j) = -z(:,j);
end
end

disp('Eigenvalues');
disp(w');
disp('Eigenvectors');
disp(z);

```
```f08he example results

Eigenvalues
-2.9943   -0.7000    1.9974    4.9969

Eigenvectors
-0.0251    0.0162    0.0113    0.9995
0.0656   -0.5859    0.8077    0.0020
0.9002   -0.3135   -0.3006    0.0311
0.4298    0.7471    0.5070   -0.0071

```

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2015