f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_zhbgst (f08usc)

## 1  Purpose

nag_zhbgst (f08usc) reduces a complex Hermitian-definite generalized eigenproblem $Az=\lambda Bz$ to the standard form $Cy=\lambda y$, where $A$ and $B$ are band matrices, $A$ is a complex Hermitian matrix, and $B$ has been factorized by nag_zpbstf (f08utc).

## 2  Specification

 #include #include
 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 $Az=\lambda Bz$ to the standard form $Cy=\lambda 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}^{\mathrm{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}^{\mathrm{H}}AX$, 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$, $Xz$ 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:     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 $X$ is to be returned.
${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$
$X$ is not returned.
${\mathbf{vect}}=\mathrm{Nag_FormX}$
$X$ is returned.
Constraint: ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$ or $\mathrm{Nag_FormX}$.
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 matrices $A$ and $B$.
Constraint: ${\mathbf{n}}\ge 0$.
5:     kaIntegerInput
On entry: if ${\mathbf{uplo}}=\mathrm{Nag_Upper}$, the number of superdiagonals, ${k}_{a}$, of the matrix $A$.
If ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, the number of subdiagonals, ${k}_{a}$, of the matrix $A$.
Constraint: ${\mathbf{ka}}\ge 0$.
6:     kbIntegerInput
On entry: if ${\mathbf{uplo}}=\mathrm{Nag_Upper}$, the number of superdiagonals, ${k}_{b}$, of the matrix $B$.
If ${\mathbf{uplo}}=\mathrm{Nag_Lower}$, the number of subdiagonals, ${k}_{b}$, of the matrix $B$.
Constraint: ${\mathbf{ka}}\ge {\mathbf{kb}}\ge 0$.
7:     ab[$\mathit{dim}$]ComplexInput/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$ 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}_{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}_{a}+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}_{a}\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}_{a}\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}_{a}\right)$;
• if ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ and ${\mathbf{uplo}}=\mathrm{Nag_Lower}$,
${A}_{ij}$ is stored in ${\mathbf{ab}}\left[{k}_{a}+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}_{a}\right),\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:     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 {\mathbf{ka}}+1$.
9:     bb[$\mathit{dim}$]const ComplexInput
Note: the dimension, dim, of the array bb must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdbb}}×{\mathbf{n}}\right)$.
On entry: the banded split Cholesky factor of $B$ as specified by uplon and kb and returned by nag_zpbstf (f08utc).
10:   pdbbIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) of the matrix in the array bb.
Constraint: ${\mathbf{pdbb}}\ge {\mathbf{kb}}+1$.
11:   x[$\mathit{dim}$]ComplexOutput
Note: the dimension, dim, of the array x must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdx}}×{\mathbf{n}}\right)$ when ${\mathbf{vect}}=\mathrm{Nag_FormX}$;
• $1$ when ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$.
The $\left(i,j\right)$th element of the matrix $X$ is stored in
• ${\mathbf{x}}\left[\left(j-1\right)×{\mathbf{pdx}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{x}}\left[\left(i-1\right)×{\mathbf{pdx}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: the $n$ by $n$ matrix $X={S}^{-1}Q$, if ${\mathbf{vect}}=\mathrm{Nag_FormX}$.
If ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, x is not referenced.
12:   pdxIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array x.
Constraints:
• if ${\mathbf{vect}}=\mathrm{Nag_FormX}$, ${\mathbf{pdx}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• if ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, ${\mathbf{pdx}}\ge 1$.
13:   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{pdx}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{n}}=⟨\mathit{\text{value}}⟩$.
Constraint: if ${\mathbf{vect}}=\mathrm{Nag_FormX}$, ${\mathbf{pdx}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
if ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, ${\mathbf{pdx}}\ge 1$.
NE_INT
On entry, ${\mathbf{ka}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ka}}\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{pdbb}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdbb}}>0$.
On entry, ${\mathbf{pdx}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdx}}>0$.
NE_INT_2
On entry, ${\mathbf{ka}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{kb}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{ka}}\ge {\mathbf{kb}}\ge 0$.
On entry, ${\mathbf{pdab}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{ka}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdab}}\ge {\mathbf{ka}}+1$.
On entry, ${\mathbf{pdbb}}=⟨\mathit{\text{value}}⟩$ and ${\mathbf{kb}}=⟨\mathit{\text{value}}⟩$.
Constraint: ${\mathbf{pdbb}}\ge {\mathbf{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  Parallelism and Performance

nag_zhbgst (f08usc) is not threaded by NAG in any implementation.
nag_zhbgst (f08usc) 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 real floating-point operations is approximately $20{n}^{2}{k}_{B}$, when ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, assuming $n\gg {k}_{A},{k}_{B}$; there are an additional $5{n}^{3}\left({k}_{B}/{k}_{A}\right)$ operations when ${\mathbf{vect}}=\mathrm{Nag_FormX}$.
The real analogue of this function is nag_dsbgst (f08uec).

## 10  Example

This example computes all the eigenvalues of $Az=\lambda Bz$, where
 $A = -1.13+0.00i 1.94-2.10i -1.40+0.25i 0.00+0.00i 1.94+2.10i -1.91+0.00i -0.82-0.89i -0.67+0.34i -1.40-0.25i -0.82+0.89i -1.87+0.00i -1.10-0.16i 0.00+0.00i -0.67-0.34i -1.10+0.16i 0.50+0.00i$
and
 $B = 9.89+0.00i 1.08-1.73i 0.00+0.00i 0.00+0.00i 1.08+1.73i 1.69+0.00i -0.04+0.29i 0.00+0.00i 0.00+0.00i -0.04-0.29i 2.65+0.00i -0.33+2.24i 0.00+0.00i 0.00+0.00i -0.33-2.24i 2.17+0.00i .$
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 $Cy=\lambda y$, then nag_zhbtrd (f08hsc) to reduce $C$ to tridiagonal form, and nag_dsterf (f08jfc) to compute the eigenvalues.

### 10.1  Program Text

Program Text (f08usce.c)

### 10.2  Program Data

Program Data (f08usce.d)

### 10.3  Program Results

Program Results (f08usce.r)