naginterfaces.library.eigen.real_​gen_​partialsvd

naginterfaces.library.eigen.real_gen_partialsvd(m, n, k, ncv, av, data=None, io_manager=None)

real_gen_partialsvd returns leading terms in the singular value decomposition (SVD) of a real general matrix and computes the corresponding left and right singular vectors.

For full information please refer to the NAG Library document for f02wg

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/f02/f02wgf.html

Parameters

mint

$m$, the number of rows of the matrix $A$.

nint

$n$, the number of columns of the matrix $A$.

kint

$k$, the number of singular values to be computed.

ncvint

This is the number of Lanczos basis vectors to use during the computation of the largest eigenvalues of $A^{T}A$ ($m\ge n$) or $A{A}^T$ ($m<n$).

At present there is no a priori analysis to guide the selection of $ncv$ relative to $k$.

However, it is recommended that $ncv\ge 2\times k+1$.

If many problems of the same type are to be solved, you should experiment with varying $ncv$ while keeping $k$ fixed for a given test problem.

This will usually decrease the required number of matrix-vector operations but it also increases the internal storage required to maintain the orthogonal basis vectors.

The optimal ‘cross-over’ with respect to CPU time is problem dependent and must be determined empirically.

avcallable (iflag, ax) = av(iflag, m, n, x, data=None)

$av$ must return the vector result of the matrix-vector product $Ax$ or $A^{T}x$, as indicated by the input value of $iflag$, for the given vector $x$.

Parameters

iflagint

If $iflag=1$, $ax$ must return the $m$-vector result of the matrix-vector product $Ax$.

If $iflag=2$, $ax$ must return the $n$-vector result of the matrix-vector product $A^{T}x$.

mint

The number of rows of the matrix $A$.

nint

The number of columns of the matrix $A$.

xfloat, ndarray, shape $(:)$

The vector to be pre-multiplied by the matrix $A$ or $A^T$.

dataarbitrary, optional, modifiable in place

User-communication data for callback functions.

Returns

iflagint

May be used as a flag to indicate a failure in the computation of $Ax$ or $A^{T}x$. If $iflag$ is negative on exit from $av$, real_gen_partialsvd will exit immediately with $\text{errno}$ set to $iflag$.

axfloat, array-like, shape $(:)$

If $iflag=1$, contains the $m$-vector result of the matrix-vector product $Ax$.

If $iflag=2$, contains the $n$-vector result of the matrix-vector product $A^{T}x$.

dataarbitrary, optional

User-communication data for callback functions.

io_managerFileObjManager, optional

Manager for I/O in this routine.

Returns

nconvint

The number of converged singular values found.

sigmafloat, ndarray, shape $\left(ncv\right)$

The $nconv$ converged singular values are stored in the first $nconv$ elements of $sigma$.

ufloat, ndarray, shape $(m,ncv)$

The left singular vectors corresponding to the singular values stored in $sigma$.

The $\text{i}$th element of the $\text{j}$th left singular vector $u_{\text{j}}$ is stored in $u[\text{i}-1,\text{j}-1]$, for $\text{j}=1,2,\dots ,nconv$, for $\text{i}=1,2,\dots ,m$.

vfloat, ndarray, shape $(n,ncv)$

The right singular vectors corresponding to the singular values stored in $sigma$.

The $\text{i}$th element of the $\text{j}$th right singular vector $v_{\text{j}}$ is stored in $v[\text{i}-1,\text{j}-1]$, for $\text{j}=1,2,\dots ,nconv$, for $\text{i}=1,2,\dots ,n$.

residfloat, ndarray, shape $\left(ncv\right)$

The residual $\Vert A{v}_j-{\sigma }_j{u}_j\Vert$, for $m\ge n$, or $\Vert A^T{u}_j-{\sigma }_j{v}_j\Vert$, for $m<n$, for each of the converged singular values ${\sigma }_j$ and corresponding left and right singular vectors $u_j$ and $v_j$.

Raises

NagValueError

(errno $i<0$)

On output from user-defined function $av$, $iflag$ was set to a negative value, $iflag=⟨value⟩$.

(errno $1$)

On entry, $m=⟨value⟩$.

Constraint: $m\ge 0$.

(errno $2$)

On entry, $n=⟨value⟩$.

Constraint: $n\ge 0$.

(errno $3$)

On entry, $k=⟨value⟩$.

Constraint: $k>0$.

(errno $4$)

On entry, $k=⟨value⟩$, $ncv=⟨value⟩$, $m=⟨value⟩$ and $n=⟨value⟩$.

Constraint: $k<ncv\le min(m,n)$.

(errno $8$)

The maximum number of iterations has been reached. The maximum number of iterations $=⟨value⟩$. The number of converged eigenvalues $=⟨value⟩$.

(errno $9$)

No shifts could be applied during a cycle of the implicitly restarted Lanczos iteration.

(errno $10$)

Could not build a full Lanczos factorization.

(errno $11$)

The number of eigenvalues found to sufficient accuracy is zero.

(errno $20$)

An error occurred during an internal call. Consider increasing the size of $ncv$ relative to $k$.

Notes

real_gen_partialsvd computes a few, $k$, of the largest singular values and corresponding vectors of an $m\times n$ matrix $A$. The value of $k$ should be small relative to $m$ and $n$, for example $k\sim O\left(min(m,n)\right)$. The full singular value decomposition (SVD) of an $m\times n$ matrix $A$ is given by

$$A=U\Sigma V^T\text{,}$$

where $U$ and $V$ are orthogonal and $\Sigma$ is an $m\times n$ diagonal matrix with real diagonal elements, ${\sigma }_i$, such that

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_{min(m,n)}\ge 0\text{.}$$

The ${\sigma }_i$ are the singular values of $A$ and the first $min(m,n)$ columns of $U$ and $V$ are the left and right singular vectors of $A$.

If $U_k$, $V_k$ denote the leading $k$ columns of $U$ and $V$ respectively, and if ${\Sigma }_k$ denotes the leading principal submatrix of $\Sigma$, then

$$A_k\equiv U_k{\Sigma }_k{V}_k^T$$

is the best rank-$k$ approximation to $A$ in both the $2$-norm and the Frobenius norm.

The singular values and singular vectors satisfy

$$A{v}_i={\sigma }_i{u}_i\text{and}{A}^T{u}_i={\sigma }_i{v}_i\text{so that}{A}^{T}A{\nu }_i={\sigma }_i^2{\nu }_i\text{and}A{A}^T{u}_i={\sigma }_i^2{u}_i\text{,}$$

where $u_i$ and $v_i$ are the $i$th columns of $U_k$ and $V_k$ respectively.

Thus, for $m\ge n$, the largest singular values and corresponding right singular vectors are computed by finding eigenvalues and eigenvectors for the symmetric matrix $A^{T}A$. For $m<n$, the largest singular values and corresponding left singular vectors are computed by finding eigenvalues and eigenvectors for the symmetric matrix $A{A}^T$. These eigenvalues and eigenvectors are found using functions from submodule sparseig. You should read the F12 Introduction for full details of the method used here.

The real matrix $A$ is not explicitly supplied to real_gen_partialsvd. Instead, you are required to supply a function, $av$, that must calculate one of the requested matrix-vector products $Ax$ or $A^{T}x$ for a given real vector $x$ (of length $n$ or $m$ respectively).

References

Wilkinson, J H, 1978, Singular Value Decomposition – Basic Aspects, Numerical Software – Needs and Availability, (ed D A H Jacobs), Academic Press