f08 Chapter Contents
f08 Chapter Introduction
NAG C Library Manual

# NAG Library Function Documentnag_dbdsdc (f08mdc)

## 1  Purpose

nag_dbdsdc (f08mdc) computes the singular values and, optionally, the left and right singular vectors of a real $n$ by $n$ (upper or lower) bidiagonal matrix $B$.

## 2  Specification

 #include #include
 void nag_dbdsdc (Nag_OrderType order, Nag_UploType uplo, Nag_ComputeSingularVecsType compq, Integer n, double d[], double e[], double u[], Integer pdu, double vt[], Integer pdvt, double q[], Integer iq[], NagError *fail)

## 3  Description

nag_dbdsdc (f08mdc) computes the singular value decomposition (SVD) of the (upper or lower) bidiagonal matrix $B$ as
 $B = USVT ,$
where $S$ is a diagonal matrix with non-negative diagonal elements ${s}_{ii}={s}_{i}$, such that
 $s1 ≥ s2 ≥ ⋯ ≥ sn ≥ 0 ,$
and $U$ and $V$ are orthogonal matrices. The diagonal elements of $S$ are the singular values of $B$ and the columns of $U$ and $V$ are respectively the corresponding left and right singular vectors of $B$.
When only singular values are required the function uses the $QR$ algorithm, but when singular vectors are required a divide and conquer method is used. The singular values can optionally be returned in compact form, although currently no function is available to apply $U$ or $V$ when stored in compact form.

## 4  References

Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J J, Du Croz J J, Greenbaum A, Hammarling S, McKenney A and Sorensen D (1999) LAPACK Users' Guide (3rd Edition) SIAM, Philadelphia http://www.netlib.org/lapack/lug
Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

## 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 Nag_ColMajor.
2:     uploNag_UploTypeInput
On entry: indicates whether $B$ is upper or lower bidiagonal.
${\mathbf{uplo}}=\mathrm{Nag_Upper}$
$B$ is upper bidiagonal.
${\mathbf{uplo}}=\mathrm{Nag_Lower}$
$B$ is lower bidiagonal.
Constraint: ${\mathbf{uplo}}=\mathrm{Nag_Upper}$ or $\mathrm{Nag_Lower}$.
3:     compqNag_ComputeSingularVecsTypeInput
On entry: specifies whether singular vectors are to be computed.
${\mathbf{compq}}=\mathrm{Nag_NotSingularVecs}$
Compute singular values only.
${\mathbf{compq}}=\mathrm{Nag_PackedSingularVecs}$
Compute singular values and compute singular vectors in compact form.
${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$
Compute singular values and singular vectors.
Constraint: ${\mathbf{compq}}=\mathrm{Nag_NotSingularVecs}$, $\mathrm{Nag_PackedSingularVecs}$ or $\mathrm{Nag_SingularVecs}$.
4:     nIntegerInput
On entry: $n$, the order of the matrix $B$.
Constraint: ${\mathbf{n}}\ge 0$.
5:     d[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array d must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$.
On entry: the $n$ diagonal elements of the bidiagonal matrix $B$.
On exit: if NE_NOERROR, the singular values of $B$.
6:     e[$\mathit{dim}$]doubleInput/Output
Note: the dimension, dim, of the array e must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}-1\right)$.
On entry: the $\left(n-1\right)$ off-diagonal elements of the bidiagonal matrix $B$.
On exit: the contents of e are destroyed.
7:     u[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array u must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdu}}×{\mathbf{n}}\right)$ when ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$;
• $1$ otherwise.
The $\left(i,j\right)$th element of the matrix $U$ is stored in
• ${\mathbf{u}}\left[\left(j-1\right)×{\mathbf{pdu}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{u}}\left[\left(i-1\right)×{\mathbf{pdu}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, then if NE_NOERROR, u contains the left singular vectors of the bidiagonal matrix $B$.
If ${\mathbf{compq}}\ne \mathrm{Nag_SingularVecs}$, u is not referenced.
8:     pduIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array u.
Constraints:
• if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdu}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise ${\mathbf{pdu}}\ge 1$.
9:     vt[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array vt must be at least
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{pdvt}}×{\mathbf{n}}\right)$ when ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$;
• $1$ otherwise.
The $\left(i,j\right)$th element of the matrix is stored in
• ${\mathbf{vt}}\left[\left(j-1\right)×{\mathbf{pdvt}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{vt}}\left[\left(i-1\right)×{\mathbf{pdvt}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, then if NE_NOERROR, the rows of vt contain the right singular vectors of the bidiagonal matrix $B$.
If ${\mathbf{compq}}\ne \mathrm{Nag_SingularVecs}$, vt is not referenced.
10:   pdvtIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array vt.
Constraints:
• if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdvt}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
• otherwise ${\mathbf{pdvt}}\ge 1$.
11:   q[$\mathit{dim}$]doubleOutput
Note: the dimension, dim, of the array q must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{{\mathbf{n}}}^{2}+5{\mathbf{n}},\mathit{ldq}\right)$, where $\mathit{ldq}$ is defined below.
On exit: if ${\mathbf{compq}}=\mathrm{Nag_PackedSingularVecs}$, then if NE_NOERROR, q and iq contain the left and right singular vectors in a compact form, requiring $\mathit{O}\left({\mathbf{n}}{\mathrm{log}}_{2}{\mathbf{n}}\right)$ space instead of $2×{{\mathbf{n}}}^{2}$. In particular, q contains all the real data in the first $\mathit{ldq}={\mathbf{n}}×\left(11+2×\mathit{smlsiz}+8×\mathrm{int}\left({\mathrm{log}}_{2}\left({\mathbf{n}}/\left(\mathit{smlsiz}+1\right)\right)\right)\right)$ elements of q, where $\mathit{smlsiz}$ is equal to the maximum size of the subproblems at the bottom of the computation tree (usually about $25$).
If ${\mathbf{compq}}\ne \mathrm{Nag_PackedSingularVecs}$, q is not referenced.
12:   iq[$\mathit{dim}$]IntegerOutput
Note: the dimension, dim, of the array iq must be at least $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,\mathit{ldiq}\right)$, where $\mathit{ldiq}$ is defined below.
On exit: if ${\mathbf{compq}}=\mathrm{Nag_PackedSingularVecs}$, then if NE_NOERROR, q and iq contain the left and right singular vectors in a compact form, requiring $\mathit{O}\left({\mathbf{n}}{\mathrm{log}}_{2}{\mathbf{n}}\right)$ space instead of $2×{{\mathbf{n}}}^{2}$. In particular, iq contains all integer data in the first $\mathit{ldiq}={\mathbf{n}}×\left(3+3×\mathrm{int}\left({\mathrm{log}}_{2}\left({\mathbf{n}}/\left(\mathit{smlsiz}+1\right)\right)\right)\right)$ elements of iq, where $\mathit{smlsiz}$ is equal to the maximum size of the subproblems at the bottom of the computation tree (usually about $25$).
If ${\mathbf{compq}}\ne \mathrm{Nag_PackedSingularVecs}$, iq is not referenced.
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{compq}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdu}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdu}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
otherwise ${\mathbf{pdu}}\ge 1$.
On entry, ${\mathbf{compq}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdvt}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{compq}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdvt}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,{\mathbf{n}}\right)$;
otherwise ${\mathbf{pdvt}}\ge 1$.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pdu}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdu}}>0$.
On entry, ${\mathbf{pdvt}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdvt}}>0$.
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.
NE_SINGULAR
The algorithm failed to compute a singular value. The update process of divide-and-conquer failed.

## 7  Accuracy

Each computed singular value of $B$ is accurate to nearly full relative precision, no matter how tiny the singular value. The $i$th computed singular value, ${\stackrel{^}{s}}_{i}$, satisfies the bound
 $s^i-si ≤ pnεsi$
where $\epsilon$ is the machine precision and $p\left(n\right)$ is a modest function of $n$.
For bounds on the computed singular values, see Section 4.9.1 of Anderson et al. (1999). See also nag_ddisna (f08flc).

If only singular values are required, the total number of floating point operations is approximately proportional to ${n}^{2}$. When singular vectors are required the number of operations is bounded above by approximately the same number of operations as nag_dbdsqr (f08mec), but for large matrices nag_dbdsdc (f08mdc) is usually much faster.
There is no complex analogue of nag_dbdsdc (f08mdc).

## 9  Example

This example computes the singular value decomposition of the upper bidiagonal matrix
 $B = 3.62 1.26 0.00 0.00 0.00 -2.41 -1.53 0.00 0.00 0.00 1.92 1.19 0.00 0.00 0.00 -1.43 .$

### 9.1  Program Text

Program Text (f08mdce.c)

### 9.2  Program Data

Program Data (f08mdce.d)

### 9.3  Program Results

Program Results (f08mdce.r)