NAG Toolbox: nag_eigen_real_gen_partialsvd (f02wg)

Purpose

Syntax

Description

References

Parameters

Compulsory Input Parameters

1:     $\mathrm{m}$ – int64int32nag_int scalar

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

Constraint: $\mathbf{m}\ge 0$.

If $\mathbf{m}=0$, an immediate return is effected.

2:     $\mathrm{n}$ – int64int32nag_int scalar

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

Constraint: $\mathbf{n}\ge 0$.

If $\mathbf{n}=0$, an immediate return is effected.

3:     $\mathrm{k}$ – int64int32nag_int scalar

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

Constraint: $0<\mathbf{k}<\min \left(\mathbf{m},\mathbf{n}\right)-1$.

4:     $\mathrm{ncv}$ – int64int32nag_int scalar

The dimension of the arrays sigma and resid and the second dimension of the arrays u and v. this is the number of Lanczos basis vectors to use during the computation of the largest eigenvalues of $A^{\mathrm{T}}A$ ($m\ge n$) or $A{A}^{\mathrm{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 $\mathbf{ncv}\ge 2\times \mathbf{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.

Constraint: $\mathbf{k}<\mathbf{ncv}\le \min \left(\mathbf{m},\mathbf{n}\right)$.

5:     $\mathrm{av}$ – function handle or string containing name of m-file

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

av is called from nag_eigen_real_gen_partialsvd (f02wg) with the argument user as supplied to nag_eigen_real_gen_partialsvd (f02wg). You are free to use these arrays to supply information to av.

[iflag, ax, user] = av(iflag, m, n, x, user)

Input Parameters

1:     $\mathrm{iflag}$ – int64int32nag_int scalar

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

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

2:     $\mathrm{m}$ – int64int32nag_int scalar

The number of rows of the matrix $A$.

3:     $\mathrm{n}$ – int64int32nag_int scalar

The number of columns of the matrix $A$.

4:     $\mathrm{x}\left(:\right)$ – double array

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

5:     $\mathrm{user}$ – Any MATLAB object

av is called from nag_eigen_real_gen_partialsvd (f02wg) with the object supplied to nag_eigen_real_gen_partialsvd (f02wg).

Output Parameters

1:     $\mathrm{iflag}$ – int64int32nag_int scalar

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

2:     $\mathrm{ax}\left(:\right)$ – double array

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

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

3:     $\mathrm{user}$ – Any MATLAB object

Optional Input Parameters

1:     $\mathrm{user}$ – Any MATLAB object

user is not used by nag_eigen_real_gen_partialsvd (f02wg), but is passed to av. Note that for large objects it may be more efficient to use a global variable which is accessible from the m-files than to use user.

Output Parameters

1:     $\mathrm{nconv}$ – int64int32nag_int scalar

The number of converged singular values found.

2:     $\mathrm{sigma}\left(\mathbf{ncv}\right)$ – double array

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

3:     $\mathrm{u}\left(\mathit{ldu},\mathbf{ncv}\right)$ – double array

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

The $\mathit{i}$th element of the $\mathit{j}$th left singular vector $u_{\mathit{j}}$ is stored in $\mathbf{u}\left(\mathit{i},\mathit{j}\right)$, for $\mathit{i}=1,2,\dots ,m$ and $\mathit{j}=1,2,\dots ,\mathbf{nconv}$.

4:     $\mathrm{v}\left(\mathit{ldv},\mathbf{ncv}\right)$ – double array

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

The $\mathit{i}$th element of the $\mathit{j}$th right singular vector $v_{\mathit{j}}$ is stored in $\mathbf{v}\left(\mathit{i},\mathit{j}\right)$, for $\mathit{i}=1,2,\dots ,n$ and $\mathit{j}=1,2,\dots ,\mathbf{nconv}$.

5:     $\mathrm{resid}\left(\mathbf{ncv}\right)$ – double array

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

6:     $\mathrm{user}$ – Any MATLAB object

7:     $\mathrm{ifail}$ – int64int32nag_int scalar

$\mathbf{ifail}=\mathbf{0}$ unless the function detects an error (see Error Indicators and Warnings).

nag_eigen_real_gen_partialsvd (f02wg) returns with $\mathbf{ifail}=\mathbf{0}$ if at least $k$ singular values have converged and the corresponding left and right singular vectors have been computed.

Error Indicators and Warnings

   $\mathbf{ifail}=1$

Constraint: $\mathbf{m}\ge 0$.

   $\mathbf{ifail}=2$

Constraint: $\mathbf{n}\ge 0$.

   $\mathbf{ifail}=3$

Constraint: $\mathbf{k}>0$.

   $\mathbf{ifail}=4$

Constraint: $\mathbf{k}<\mathbf{ncv}\le \min \left(\mathbf{m},\mathbf{n}\right)$.

   $\mathbf{ifail}=5$

Constraint: $\mathit{ldu}\ge \mathbf{m}$.

   $\mathbf{ifail}=6$

Constraint: $\mathit{ldv}\ge \mathbf{n}$.

   $\mathbf{ifail}=8$

The maximum number of iterations has been reached.

   $\mathbf{ifail}=9$

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

   $\mathbf{ifail}=10$

Could not build a full Lanczos factorization.

   $\mathbf{ifail}=11$

The number of eigenvalues found to sufficient accuracy is zero.

   $\mathbf{ifail}=20$

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

   $\mathbf{ifail}<0$

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

   $\mathbf{ifail}=-99$

An unexpected error has been triggered by this routine. Please contact NAG.

   $\mathbf{ifail}=-399$

Your licence key may have expired or may not have been installed correctly.

   $\mathbf{ifail}=-999$

Dynamic memory allocation failed.

Accuracy

Further Comments

Example

Open in the MATLAB editor: f02wg_example

function f02wg_example


fprintf('f02wg example results\n\n');

m = int64(100);
n = int64(500);
k = int64(4);
ncv = int64(10);

[nconv, sigma, u, v, resid, user, ifail] = ...
f02wg(m, n, k, ncv, @av);

res = [sigma(1:nconv) resid(1:nconv)];
fprintf('  Singular Value   Residual\n');
fprintf('   %10.5f  %12.2e\n',res');



function [iflag, ax, user] = av(iflag, m, n, x, user)
  if (iflag == 1)
    ax = zeros(m, 1);
  else
    ax = zeros(n, 1);
  end

  % Computes  w <- A*x or w <- Trans(A)*x.
  h = 1/(double(m)+1);
  k = 1/(double(n)+1);
  if (iflag == 1)
    t = 0;
    for j = 1:n
      t = t + k;
      s = 0;
      ktx = k*(t-1)*x(j);
      for i = 1:min(j,m)
        s = s + h;
        ax(i) = ax(i) + ktx*s;
      end
      ktx = k*t*x(j);
      for i = j+1:m
        s = s + h;
        ax(i) = ax(i) + ktx*(s-1);
      end
    end
  else
    t = 0;
    for j = 1:n
      t = t + k;
      s = 0;
      for i = 1:min(j,m)
        s = s + h;
        ax(j) = ax(j) + k*s*(t-1)*x(i);
      end
      for i = j+1:m
        s = s + h;
        ax(j) = ax(j) + k*t*(s-1)*x(i);
      end
    end
  end

f02wg example results

  Singular Value   Residual
      0.00830      1.82e-18
      0.01223      3.95e-18
      0.02381      1.95e-17
      0.11274      2.53e-17