# NAG CL Interfacef08mbc (dbdsvdx)

## 1Purpose

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

## 2Specification

 #include
 void f08mbc (Nag_OrderType order, Nag_UploType uplo, Nag_ComputeSingularVecsType jobz, Nag_RangeType range, Integer n, const double d[], const double e[], double vl, double vu, Integer il, Integer iu, Integer *ns, double s[], double z[], Integer pdz, Integer jfail[], NagError *fail)
The function may be called by the names: f08mbc, nag_lapackeig_dbdsvdx or nag_dbdsvdx.

## 3Description

f08mbc computes the singular value decomposition (SVD) of a real $n$ by $n$ (upper or lower) bidiagonal matrix $B$ as
 $B = USVT ,$
where $S$ is a diagonal matrix with non-negative diagonal elements (the singular values of $B$), and $U$ and ${V}^{\mathrm{T}}$ are orthogonal matrices. The columns of $U$ and $V$ are the left and right singular vectors of $B$, respectively.
Given an upper bidiagonal matrix $B$ with diagonal $\mathbit{d}=\left(\begin{array}{cccc}{d}_{1}& {d}_{2}& \dots & {d}_{n}\end{array}\right)$ and superdiagonal $\mathbit{e}=\left(\begin{array}{cccc}{e}_{1}& {e}_{2}& \dots & {e}_{N-1}\end{array}\right)$, f08mbc computes the singular value decomposition of $B$ through the eigenvalues and eigenvectors of the $n×2$ by $n×2$ tridiagonal matrix
 $TGK= 0 d1 d1 0 e1 e1 0 d2 d2 . . . . .$
If $\left(s,u,v\right)$ is a singular triplet of $B$ with $‖u‖=‖v‖=1$, then $\left(s,{q}_{1}\right)$ and $\left(-s,{q}_{2}\right)$, $‖{q}_{1}‖=‖{q}_{2}‖=1$, are eigenpairs of $\mathit{TGK}$, with ${q}_{1}=\left({v}_{1},{u}_{1},{v}_{2},{u}_{2},\dots ,{v}_{n},{u}_{n}\right)/\sqrt{2}$, and ${q}_{2}=\left({-v}_{1},{u}_{1},{-v}_{2},{u}_{2},\dots ,{-v}_{n},{u}_{n}\right)/\sqrt{2}$.
Given a $\mathit{TGK}$ matrix, you can either
1. (i)compute $-s,-v$ and change signs so that the singular values (and corresponding vectors) are already in descending order (as in f08kbc) or
2. (ii)compute $s,v$ and reorder the values (and corresponding vectors).
f08mbc implements (i) by calling f08jbc (bisection plus inverse iteration, to be replaced with a version of the Multiple Relative Robust Representation algorithm. (See Williams and Lang (2013).)
Alternative to computing all singular values of $B$, a selected set can be computed. The set is either those singular values lying in a given interval, $\sigma \in \left({v}_{l},{v}_{u}\right]$, or those whose index (counting from largest to smallest in magnitude) lies in a given range $1\le {i}_{l},\dots ,{i}_{u}\le n$. In these cases, the corresponding left and right singular vectors can optionally be computed.

## 4References

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 https://www.netlib.org/lapack/lug
Williams P and Lang B (2013) A framework for the $M{R}^{3}$ Algorithm: theory and implementation SIAM J. Sci. Comput. 35 740–766

## 5Arguments

1: $\mathbf{order}$Nag_OrderType Input
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.1.3 in the Introduction to the NAG Library CL Interface for a more detailed explanation of the use of this argument.
Constraint: ${\mathbf{order}}=\mathrm{Nag_RowMajor}$ or $\mathrm{Nag_ColMajor}$.
2: $\mathbf{uplo}$Nag_UploType Input
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: $\mathbf{jobz}$Nag_ComputeSingularVecsType Input
On entry: indicates whether singular vectors are computed.
${\mathbf{jobz}}=\mathrm{Nag_NotSingularVecs}$
Only singular values are computed.
${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$
Singular values and singular vectors are computed.
Constraint: ${\mathbf{jobz}}=\mathrm{Nag_NotSingularVecs}$ or $\mathrm{Nag_SingularVecs}$.
4: $\mathbf{range}$Nag_RangeType Input
On entry: indicates which singular values should be returned.
${\mathbf{range}}=\mathrm{Nag_AllValues}$
All singular values will be found.
${\mathbf{range}}=\mathrm{Nag_Interval}$
All singular values in the half-open interval $\left({\mathbf{vl}},{\mathbf{vu}}\right]$ will be found.
${\mathbf{range}}=\mathrm{Nag_Indices}$
The ilth through iuth singular values will be found.
Constraint: ${\mathbf{range}}=\mathrm{Nag_AllValues}$, $\mathrm{Nag_Interval}$ or $\mathrm{Nag_Indices}$.
5: $\mathbf{n}$Integer Input
On entry: $n$, the order of the bidiagonal matrix $B$.
Constraint: ${\mathbf{n}}\ge 0$.
6: $\mathbf{d}\left[{\mathbf{n}}\right]$const double Input
On entry: the diagonal elements $\mathbit{d}$ of the bidiagonal matrix $B$.
7: $\mathbf{e}\left[{\mathbf{n}}-1\right]$const double Input
On entry: the $\left(n-1\right)$ off-diagonal elements $\mathbit{e}$ of the bidiagonal matrix $B$.
8: $\mathbf{vl}$double Input
On entry: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, the lower bound of the interval to be searched for singular values.
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Indices}$, vl is not referenced.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, $0.0\le {\mathbf{vl}}$.
9: $\mathbf{vu}$double Input
On entry: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, the upper bound of the interval to be searched for singular values.
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Indices}$, vu is not referenced.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, ${\mathbf{vl}}<{\mathbf{vu}}$.
10: $\mathbf{il}$Integer Input
11: $\mathbf{iu}$Integer Input
On entry: if ${\mathbf{range}}=\mathrm{Nag_Indices}$, il and iu specify the indices (in ascending order) of the smallest and largest singular values to be returned, respectively.
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$ or $\mathrm{Nag_Interval}$, il and iu are not referenced.
Constraints:
• if ${\mathbf{range}}=\mathrm{Nag_Indices}$ and ${\mathbf{n}}=0$, ${\mathbf{il}}=1$ and ${\mathbf{iu}}=0$;
• if ${\mathbf{range}}=\mathrm{Nag_Indices}$ and ${\mathbf{n}}>0$, $1\le {\mathbf{il}}\le {\mathbf{iu}}\le {\mathbf{n}}$.
12: $\mathbf{ns}$Integer * Output
On exit: the total number of singular values found. $0\le {\mathbf{ns}}\le {\mathbf{n}}$.
If ${\mathbf{range}}=\mathrm{Nag_AllValues}$, ${\mathbf{ns}}={\mathbf{n}}$.
If ${\mathbf{range}}=\mathrm{Nag_Indices}$, ${\mathbf{ns}}={\mathbf{iu}}-{\mathbf{il}}+1$.
13: $\mathbf{s}\left[{\mathbf{n}}\right]$double Output
On exit: the first ns elements contain the selected singular values in ascending order.
14: $\mathbf{z}\left[\mathit{dim}\right]$double Output
Note: the dimension, dim, of the array z must be at least
• ${\mathbf{pdz}}×\left(\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},{\mathbf{ns}}+1\right)\right)$ when ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$ and ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• $\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(1,\mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(2,{\mathbf{n}}×2\right)×{\mathbf{pdz}}\right)$ when ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$ and ${\mathbf{order}}=\mathrm{Nag_RowMajor}$;
• $1$ otherwise.
The $\left(i,j\right)$th element of the matrix $Z$ is stored in
• ${\mathbf{z}}\left[\left(j-1\right)×{\mathbf{pdz}}+i-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_ColMajor}$;
• ${\mathbf{z}}\left[\left(i-1\right)×{\mathbf{pdz}}+j-1\right]$ when ${\mathbf{order}}=\mathrm{Nag_RowMajor}$.
On exit: if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, then if ${\mathbf{fail}}\mathbf{.}\mathbf{errnum}=0$ the first ns columns of z contain the singular vectors of the matrix $B$ corresponding to the selected singular values, with $U$ in rows $1$ to $n$ and $V$ in rows $n+1$ to $n×2$, i.e.,
 $Z= U V .$
If ${\mathbf{jobz}}=\mathrm{Nag_NotSingularVecs}$, then z is not referenced.
Note: the user must ensure that at least $K=\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},{\mathbf{ns}}\right)+1$ columns are supplied in the array $Z$. If ${\mathbf{range}}=\mathrm{Nag_Interval}$, the exact value of ns is not known in advance and an upper bound of at least n must be used.
15: $\mathbf{pdz}$Integer Input
On entry: the stride separating row or column elements (depending on the value of order) in the array z.
Constraints:
• if ${\mathbf{order}}=\mathrm{Nag_ColMajor}$,
• if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(2,{\mathbf{n}}×2\right)$;
• otherwise ${\mathbf{pdz}}\ge 1$;
• if ${\mathbf{order}}=\mathrm{Nag_RowMajor}$,
• if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdz}}\ge \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},{\mathbf{ns}}+1\right)$;
• otherwise ${\mathbf{pdz}}\ge 1$.
16: $\mathbf{jfail}\left[2×{\mathbf{n}}\right]$Integer Output
On exit: if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, then
• if ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_NOERROR, the first ns elements of jfail are zero;
• if ${\mathbf{fail}}\mathbf{.}\mathbf{code}=$ NE_CONVERGENCE, jfail contains the indices of the eigenvectors that failed to converge in f08jbc.
If ${\mathbf{jobz}}=\mathrm{Nag_NotSingularVecs}$, jfail is not referenced.
17: $\mathbf{fail}$NagError * Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).

## 6Error Indicators and Warnings

NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
On entry, argument $〈\mathit{\text{value}}〉$ had an illegal value.
NE_CONVERGENCE
The algorithm failed to converge; $〈\mathit{\text{value}}〉$ eigenvectors of the associated eigenproblem did not converge. Their indices are stored in array jfail.
NE_ENUM_INT
On entry, ${\mathbf{jobz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},{\mathbf{ns}}+1\right)>0$.
NE_ENUM_INT_2
On entry, ${\mathbf{jobz}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdz}}\ge \mathrm{max}\phantom{\rule{0.125em}{0ex}}\left(2,{\mathbf{n}}×2\right)$;
otherwise ${\mathbf{pdz}}\ge 1$.
On entry, ${\mathbf{jobz}}=〈\mathit{\text{value}}〉$, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{jobz}}=\mathrm{Nag_SingularVecs}$, ${\mathbf{pdz}}\ge \mathrm{min}\phantom{\rule{0.125em}{0ex}}\left({\mathbf{n}},{\mathbf{ns}}+1\right)$;
otherwise ${\mathbf{pdz}}\ge 1$.
NE_ENUM_INT_3
On entry, ${\mathbf{range}}=〈\mathit{\text{value}}〉$, ${\mathbf{il}}=〈\mathit{\text{value}}〉$, ${\mathbf{iu}}=〈\mathit{\text{value}}〉$ and ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Indices}$ and ${\mathbf{n}}=0$, ${\mathbf{il}}=1$ and ${\mathbf{iu}}=0$;
if ${\mathbf{range}}=\mathrm{Nag_Indices}$ and ${\mathbf{n}}>0$, $1\le {\mathbf{il}}\le {\mathbf{iu}}\le {\mathbf{n}}$.
NE_ENUM_REAL_1
On entry, ${\mathbf{range}}=〈\mathit{\text{value}}〉$ and ${\mathbf{vl}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, $0.0\le {\mathbf{vl}}$.
NE_ENUM_REAL_2
On entry, ${\mathbf{range}}=〈\mathit{\text{value}}〉$, ${\mathbf{vl}}=〈\mathit{\text{value}}〉$ and ${\mathbf{vu}}=〈\mathit{\text{value}}〉$.
Constraint: if ${\mathbf{range}}=\mathrm{Nag_Interval}$, ${\mathbf{vl}}<{\mathbf{vu}}$.
NE_INT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 0$.
On entry, ${\mathbf{pdz}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{pdz}}>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.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.

## 7Accuracy

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 vectors, see Section 4.9.1 of Anderson et al. (1999). See also f08flc.

## 8Parallelism and Performance

f08mbc is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
f08mbc 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.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.

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 f08mec, but for large matrices f08mbc is usually much faster.
There is no complex analogue of f08mbc.

## 10Example

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 .$

### 10.1Program Text

Program Text (f08mbce.c)

### 10.2Program Data

Program Data (f08mbce.d)

### 10.3Program Results

Program Results (f08mbce.r)