NAG Library Function Document

nag_zhbgst (f08usc)

void	nag_zhbgst (Nag_OrderType order, Nag_VectType vect, Nag_UploType uplo, Integer n, Integer ka, Integer kb, Complex ab[], Integer pdab, const Complex bb[], Integer pdbb, Complex x[], Integer pdx, NagError *fail)

3 Description

To reduce the complex Hermitian-definite generalized eigenproblem

A z = λ B z

to the standard form

C y = λ y

, where

A

B

and

C

are banded, nag_zhbgst (f08usc) must be preceded by a call to nag_zpbstf (f08utc) which computes the split Cholesky factorization of the positive definite matrix

B

B = S^{H} S

. The split Cholesky factorization, compared with the ordinary Cholesky factorization, allows the work to be approximately halved.

This function overwrites

A

with

C = X^{H} A X

, where

X = S^{- 1} Q

and

Q

is a unitary matrix chosen (implicitly) to preserve the bandwidth of

A

. The function also has an option to allow the accumulation of

X

, and then, if

z

is an eigenvector of

C

X z

is an eigenvector of the original system.

4 References

Crawford C R (1973) Reduction of a band-symmetric generalized eigenvalue problem Comm. ACM 16 41–44

Kaufman L (1984) Banded eigenvalue solvers on vector machines ACM Trans. Math. Software 10 73–86

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

X

is to be returned.

$vect = Nag_DoNotForm$: $X$ is not returned.
$vect = Nag_FormX$: $X$ is returned.

Constraint:

vect = Nag_DoNotForm

Nag_FormX

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 matrices

A

and

B

Constraint:

n \geq 0

5: ka – IntegerInput

On entry: if

uplo = Nag_Upper

, the number of superdiagonals,

k_{a}

, of the matrix

A

uplo = Nag_Lower

, the number of subdiagonals,

k_{a}

, of the matrix

A

Constraint:

ka \geq 0

6: kb – IntegerInput

On entry: if

uplo = Nag_Upper

, the number of superdiagonals,

k_{b}

, of the matrix

B

uplo = Nag_Lower

, the number of subdiagonals,

k_{b}

, of the matrix

B

Constraint:

ka \geq kb \geq 0

7: ab[ $\dim$ ] – ComplexInput/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

Hermitian 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_{a} + i - j + (j - 1) \times pdab]$ , for $j = 1, \dots, n$ and $i = \max (1, j - k_{a}), \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_{a})$ ;
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_{a})$ ;
if $order = Nag_RowMajor$ and $uplo = Nag_Lower$ ,
$A_{i j}$ is stored in $ab [k_{a} + j - i + (i - 1) \times pdab]$ , for $i = 1, \dots, n$ and $j = \max (1, i - k_{a}), \dots, i$ .

On exit: the upper or lower triangle of ab is overwritten by the corresponding upper or lower triangle of

C

as specified by uplo.

8: 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 ka + 1

9: bb[ $\dim$ ] – const ComplexInput

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

\max (1, pdbb \times n)

On entry: the banded split Cholesky factor of

B

as specified by uplo, n and kb and returned by nag_zpbstf (f08utc).

10: pdbb – IntegerInput

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

Constraint:

pdbb \geq kb + 1

11: x[ $\dim$ ] – ComplexOutput

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

$\max (1, pdx \times n)$ when $vect = Nag_FormX$ ;
$1$ when $vect = Nag_DoNotForm$ .

The

(i, j)

th element of the matrix

X

is stored in

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

On exit: the

n

n

matrix

X = S^{- 1} Q

, if

vect = Nag_FormX

vect = Nag_DoNotForm

, x is not referenced.

12: pdx – IntegerInput

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

Constraints:

if $vect = Nag_FormX$ , $pdx \geq \max (1, n)$ ;
if $vect = Nag_DoNotForm$ , $pdx \geq 1$ .

13: 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〉$ , $pdx = 〈value〉$ and $n = 〈value〉$ .
Constraint: if $vect = Nag_FormX$ , $pdx \geq \max (1, n)$ ;
if $vect = Nag_DoNotForm$ , $pdx \geq 1$ .
NE_INT: On entry, $ka = 〈value〉$ .
Constraint: $ka \geq 0$ .; On entry, $n = 〈value〉$ .
Constraint: $n \geq 0$ .; On entry, $pdab = 〈value〉$ .
Constraint: $pdab > 0$ .; On entry, $pdbb = 〈value〉$ .
Constraint: $pdbb > 0$ .; On entry, $pdx = 〈value〉$ .
Constraint: $pdx > 0$ .
NE_INT_2: On entry, $ka = 〈value〉$ and $kb = 〈value〉$ .
Constraint: $ka \geq kb \geq 0$ .; On entry, $pdab = 〈value〉$ and $ka = 〈value〉$ .
Constraint: $pdab \geq ka + 1$ .; On entry, $pdbb = 〈value〉$ and $kb = 〈value〉$ .
Constraint: $pdbb \geq kb + 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

Forming the reduced matrix

C

is a stable procedure. However it involves implicit multiplication by

B^{- 1}

. When nag_zhbgst (f08usc) is used as a step in the computation of eigenvalues and eigenvectors of the original problem, there may be a significant loss of accuracy if

B

is ill-conditioned with respect to inversion.

8 Further Comments

The total number of real floating point operations is approximately

20 n^{2} k_{B}

, when

vect = Nag_DoNotForm

, assuming

n ≫ k_{A}, k_{B}

; there are an additional

5 n^{3} (k_{B} / k_{A})

operations when

vect = Nag_FormX

The real analogue of this function is nag_dsbgst (f08uec).

9 Example

This example computes all the eigenvalues of

A z = λ B z

, where

A = (\begin{array}{r} - 1.13 + 0.00 i & 1.94 - 2.10 i & - 1.40 + 0.25 i & 0.00 + 0.00 i \\ 1.94 + 2.10 i & - 1.91 + 0.00 i & - 0.82 - 0.89 i & - 0.67 + 0.34 i \\ - 1.40 - 0.25 i & - 0.82 + 0.89 i & - 1.87 + 0.00 i & - 1.10 - 0.16 i \\ 0.00 + 0.00 i & - 0.67 - 0.34 i & - 1.10 + 0.16 i & 0.50 + 0.00 i \end{array})

and

B = (\begin{array}{r} 9.89 + 0.00 i & 1.08 - 1.73 i & 0.00 + 0.00 i & 0.00 + 0.00 i \\ 1.08 + 1.73 i & 1.69 + 0.00 i & - 0.04 + 0.29 i & 0.00 + 0.00 i \\ 0.00 + 0.00 i & - 0.04 - 0.29 i & 2.65 + 0.00 i & - 0.33 + 2.24 i \\ 0.00 + 0.00 i & 0.00 + 0.00 i & - 0.33 - 2.24 i & 2.17 + 0.00 i \end{array}) .

Here

A

is Hermitian,

B

is Hermitian positive definite, and

A

and

B

are treated as band matrices.

B

must first be factorized by nag_zpbstf (f08utc). The program calls nag_zhbgst (f08usc) to reduce the problem to the standard form

C y = λ y

, then nag_zhbtrd (f08hsc) to reduce

C

to tridiagonal form, and nag_dsterf (f08jfc) to compute the eigenvalues.

NAG Library Function Documentnag_zhbgst (f08usc)

+− 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_zhbgst (f08usc)