f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

# NAG Library Function Documentnag_dsbgst (f08uec)

## 1  Purpose

nag_dsbgst (f08uec) reduces a real symmetric-definite generalized eigenproblem $Az=\lambda Bz$ to the standard form $Cy=\lambda y$, where $A$ and $B$ are band matrices, $A$ is a real symmetric matrix, and $B$ has been factorized by nag_dpbstf (f08ufc).

## 2  Specification

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

## 3  Description

To reduce the real symmetric-definite generalized eigenproblem $Az=\lambda Bz$ to the standard form $Cy=\lambda y$, where $A$, $B$ and $C$ are banded, nag_dsbgst (f08uec) must be preceded by a call to nag_dpbstf (f08ufc) which computes the split Cholesky factorization of the positive definite matrix $B$: $B={S}^{\mathrm{T}}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{T}}AX$, where $X={S}^{-1}Q$ and $Q$ is a orthogonal 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}$]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}_{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 doubleInput
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_dpbstf (f08ufc).
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}$]doubleOutput
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_dsbgst (f08uec) 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_dsbgst (f08uec) is not threaded by NAG in any implementation.
nag_dsbgst (f08uec) 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}_{B}$, when ${\mathbf{vect}}=\mathrm{Nag_DoNotForm}$, assuming $n\gg {k}_{A},{k}_{B}$; there are an additional $\left(3/2\right){n}^{3}\left({k}_{B}/{k}_{A}\right)$ operations when ${\mathbf{vect}}=\mathrm{Nag_FormX}$.
The complex analogue of this function is nag_zhbgst (f08usc).

## 10  Example

This example computes all the eigenvalues of $Az=\lambda Bz$, where
 $A = 0.24 0.39 0.42 0.00 0.39 -0.11 0.79 0.63 0.42 0.79 -0.25 0.48 0.00 0.63 0.48 -0.03 and B= 2.07 0.95 0.00 0.00 0.95 1.69 -0.29 0.00 0.00 -0.29 0.65 -0.33 0.00 0.00 -0.33 1.17 .$
Here $A$ is symmetric, $B$ is symmetric positive definite, and $A$ and $B$ are treated as band matrices. $B$ must first be factorized by nag_dpbstf (f08ufc). The program calls nag_dsbgst (f08uec) to reduce the problem to the standard form $Cy=\lambda y$, then nag_dsbtrd (f08hec) to reduce $C$ to tridiagonal form, and nag_dsterf (f08jfc) to compute the eigenvalues.

### 10.1  Program Text

Program Text (f08uece.c)

### 10.2  Program Data

Program Data (f08uece.d)

### 10.3  Program Results

Program Results (f08uece.r)