nag_dsbtrd (f08hec) : NAG Library, Mark 23

3 Description

nag_dsbtrd (f08hec) reduces a symmetric band matrix

A

to symmetric tridiagonal form

T

by an orthogonal similarity transformation:

T = Q^{T} 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).

5 Arguments

1: order – Nag_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

order = Nag_RowMajor

. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.

Constraint:

order = Nag_RowMajor

or Nag_ColMajor.

2: vect – Nag_VectTypeInput

On entry: indicates whether

Q

is to be returned.

$vect = Nag_FormQ$: $Q$ is returned.
$vect = Nag_UpdateQ$: $Q$ is updated (and the array q must contain a matrix on entry).
$vect = Nag_DoNotForm$: $Q$ is not required.

Constraint:

vect = Nag_FormQ

Nag_UpdateQ

Nag_DoNotForm

3: uplo – Nag_UploTypeInput

On entry: indicates whether the upper or lower triangular part of

A

is stored.

$uplo = Nag_Upper$: The upper triangular part of $A$ is stored.
$uplo = Nag_Lower$: The lower triangular part of $A$ is stored.

Constraint:

uplo = Nag_Upper

Nag_Lower

4: n – IntegerInput

On entry:

n

, the order of the matrix

A

Constraint:

n \geq 0

5: kd – IntegerInput

On entry: if

uplo = Nag_Upper

, the number of superdiagonals,

k_{d}

, of the matrix

A

uplo = Nag_Lower

, the number of subdiagonals,

k_{d}

, of the matrix

A

Constraint:

kd \geq 0

6: ab[

\dim

] – doubleInput/Output

Note: the dimension, dim, of the array ab must be at least

\max (1, pdab \times n)

On entry: the upper or lower triangle of the

n

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_{i j}

, depends on the order and uplo arguments as follows:

if $order = Nag_ColMajor$ and $uplo = Nag_Upper$ ,
$A_{i j}$ is stored in $ab [k_{d} + i - j + (j - 1) \times pdab]$ , for $j = 1, \dots, n$ and $i = \max (1, j - k_{d}), \dots, j$ ;
if $order = Nag_ColMajor$ and $uplo = Nag_Lower$ ,
$A_{i j}$ is stored in $ab [i - j + (j - 1) \times pdab]$ , for $j = 1, \dots, n$ and $i = j, \dots, \min (n, j + k_{d})$ ;
if $order = Nag_RowMajor$ and $uplo = Nag_Upper$ ,
$A_{i j}$ is stored in $ab [j - i + (i - 1) \times pdab]$ , for $i = 1, \dots, n$ and $j = i, \dots, \min (n, i + k_{d})$ ;
if $order = Nag_RowMajor$ and $uplo = Nag_Lower$ ,
$A_{i j}$ is stored in $ab [k_{d} + j - i + (i - 1) \times pdab]$ , for $i = 1, \dots, n$ and $j = \max (1, i - k_{d}), \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: pdab – IntegerInput

On entry: the stride separating row or column elements (depending on the value of order) of the matrix

A

in the array ab.

Constraint:

pdab \geq \max (1, kd + 1)

8: d[n] – doubleOutput

On exit: the diagonal elements of the tridiagonal matrix

T

9: e[

n - 1

] – doubleOutput

On exit: the off-diagonal elements of the tridiagonal matrix

T

10: q[

\dim

] – doubleInput/Output

Note: the dimension, dim, of the array q must be at least

$\max (1, pdq \times n)$ when $vect = Nag_FormQ$ or $Nag_UpdateQ$ ;
$1$ when $vect = Nag_DoNotForm$ .

The

(i, j)

th element of the matrix

Q

is stored in

$q [(j - 1) \times pdq + i - 1]$ when $order = Nag_ColMajor$ ;
$q [(i - 1) \times pdq + j - 1]$ when $order = Nag_RowMajor$ .

On entry: if

vect = 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

vect = Nag_FormQ

Nag_UpdateQ

, the

n

n

matrix

Q

vect = Nag_DoNotForm

, q is not referenced.

11: pdq – IntegerInput

On entry: the stride separating row or column elements (depending on the value of order) in the array q.

Constraints:

if $vect = Nag_FormQ$ or $Nag_UpdateQ$ , $pdq \geq \max (1, n)$ ;
if $vect = Nag_DoNotForm$ , $pdq \geq 1$ .

12: fail – NagError *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.

NE_BAD_PARAM

On entry, argument

〈value〉

had an illegal value.

NE_ENUM_INT_2

On entry,

vect = 〈value〉

pdq = 〈value〉

and

n = 〈value〉

.
Constraint: if

vect = Nag_FormQ

Nag_UpdateQ

pdq \geq \max (1, n)

;
if

vect = Nag_DoNotForm

pdq \geq 1

NE_INT

On entry,

kd = 〈value〉

.
Constraint:

kd \geq 0

On entry,

n = 〈value〉

.
Constraint:

n \geq 0

On entry,

pdab = 〈value〉

.
Constraint:

pdab > 0

On entry,

pdq = 〈value〉

.
Constraint:

pdq > 0

NE_INT_2

On entry,

pdab = 〈value〉

and

kd = 〈value〉

.
Constraint:

pdab \geq \max (1, kd + 1)

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

(A + E)

, where

{‖E‖}_{2} \leq c (n) ε {‖A‖}_{2},

c (n)

is a modestly increasing function of

n

, and

ε

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

{‖E‖}_{2} = O (ε),

where

ε

is the machine precision.

9 Example

This example computes all the eigenvalues and eigenvectors of the matrix

A

, where

A = (\begin{array}{r} 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 \end{array}) .

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

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Function Document

nag_dsbtrd (f08hec)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Function Documentnag_dsbtrd (f08hec)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Function Document

nag_dsbtrd (f08hec)