nag_dgesvj (f08kjc) (PDF version)
f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_dgesvj (f08kjc)

+ Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_dgesvj (f08kjc) computes the one-sided Jacobi singular value decomposition (SVD) of a real m by n matrix A, mn, with fast scaled rotations and de Rijk’s pivoting, optionally computing the left and/or right singular vectors. For m<n, the functions nag_dgesvd (f08kbc) or nag_dgesdd (f08kdc) may be used.

2  Specification

#include <nag.h>
#include <nagf08.h>
void  nag_dgesvj (Nag_OrderType order, Nag_MatrixType joba, Nag_LeftVecsType jobu, Nag_RightVecsType jobv, Integer m, Integer n, double a[], Integer pda, double sva[], Integer mv, double v[], Integer pdv, double work[], Integer lwork, NagError *fail)

3  Description

The SVD is written as
A = UΣVT ,
where Σ is an n by n diagonal matrix, U is an m by n orthonormal matrix, and V is an n by n orthogonal matrix. The diagonal elements of Σ are the singular values of A in descending order of magnitude. The columns of U and V are the left and the right singular vectors of A.

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
Drmac Z and Veselic K (2008a) New fast and accurate Jacobi SVD algorithm I SIAM J. Matrix Anal. Appl. 29 4
Drmac Z and Veselic K (2008b) New fast and accurate Jacobi SVD algorithm II SIAM J. Matrix Anal. Appl. 29 4
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 order=Nag_RowMajor. See Section 3.2.1.3 in the Essential Introduction for a more detailed explanation of the use of this argument.
Constraint: order=Nag_RowMajor or Nag_ColMajor.
2:     jobaNag_MatrixTypeInput
On entry: specifies the structure of matrix A.
joba=Nag_LowerMatrix
The input matrix A is lower triangular.
joba=Nag_UpperMatrix
The input matrix A is upper triangular.
joba=Nag_GeneralMatrix
The input matrix A is a general m by n matrix, mn.
Constraint: joba=Nag_LowerMatrix, Nag_UpperMatrix or Nag_GeneralMatrix.
3:     jobuNag_LeftVecsTypeInput
On entry: specifies whether to compute the left singular vectors and if so whether you want to control their numerical orthogonality threshold.
jobu=Nag_LeftSpan
The left singular vectors corresponding to the nonzero singular values are computed and returned in the leading columns of a. See more details in the description of a. The numerical orthogonality threshold is set to approximately tol=ctol×ε, where ε is the machine precision and ctol=m.
jobu=Nag_LeftVecsCtol
Analogous to jobu=Nag_LeftSpan, except that you can control the level of numerical orthogonality of the computed left singular vectors. The orthogonality threshold is set to tol=ctol×ε, where ctol is given on input in work[0]. The option jobu=Nag_LeftVecsCtol can be used if m×ε is a satisfactory orthogonality of the computed left singular vectors, so ctol=m could save a few sweeps of Jacobi rotations. See the descriptions of a and work[0].
jobu=Nag_NotLeftVecs
The matrix U is not computed. However, see the description of a.
Constraint: jobu=Nag_LeftSpan, Nag_LeftVecsCtol or Nag_NotLeftVecs.
4:     jobvNag_RightVecsTypeInput
On entry: specifies whether and how to compute the right singular vectors.
jobv=Nag_RightVecs
The matrix V is computed and returned in the array v.
jobv=Nag_RightVecsMV
The Jacobi rotations are applied to the leading mv by n part of the array v. In other words, the right singular vector matrix V is not computed explicitly, instead it is applied to an mv by n matrix initially stored in the first mv rows of v.
jobv=Nag_NotRightVecs
The matrix V is not computed and the array v is not referenced.
Constraint: jobv=Nag_RightVecs, Nag_RightVecsMV or Nag_NotRightVecs.
5:     mIntegerInput
On entry: m, the number of rows of the matrix A.
Constraint: m0.
6:     nIntegerInput
On entry: n, the number of columns of the matrix A.
Constraint: mn0.
7:     a[dim]doubleInput/Output
Note: the dimension, dim, of the array a must be at least
  • max1,pda×n when order=Nag_ColMajor;
  • max1,m×pda when order=Nag_RowMajor.
The i,jth element of the matrix A is stored in
  • a[j-1×pda+i-1] when order=Nag_ColMajor;
  • a[i-1×pda+j-1] when order=Nag_RowMajor.
On entry: the m by n matrix A.
On exit: the matrix U containing the left singular vectors of A.
If jobu=Nag_LeftSpan or Nag_LeftVecsCtol
if fail.errnum=0
rankA orthonormal columns of U are returned in the leading rankA columns of the array a. Here rankAn is the number of computed singular values of A that are above the safe range parameter, as returned by nag_real_safe_small_number (X02AMC). The singular vectors corresponding to underflowed or zero singular values are not computed. The value of rankA is returned by rounding work[1] to the nearest whole number. Also see the descriptions of sva and work. The computed columns of U are mutually numerically orthogonal up to approximately tol=m×ε; or tol=ctol×ε (jobu=Nag_LeftVecsCtol), where ε is the machine precision and ctol is supplied on entry in work[0], see the description of jobu.
If fail.errnum>0
nag_dgesvj (f08kjc) did not converge in 30 iterations (sweeps). In this case, the computed columns of U may not be orthogonal up to tol. The output U (stored in a), Σ (given by the computed singular values in sva) and V is still a decomposition of the input matrix A in the sense that the residual A-α×U×Σ×VT2/A2 is small, where α is the value returned in work[0].
If jobu=Nag_NotLeftVecs
if fail.errnum=0
Note that the left singular vectors are ‘for free’ in the one-sided Jacobi SVD algorithm. However, if only the singular values are needed, the level of numerical orthogonality of U is not an issue and iterations are stopped when the columns of the iterated matrix are numerically orthogonal up to approximately m×ε. Thus, on exit, a contains the columns of U scaled with the corresponding singular values.
If fail.errnum>0
nag_dgesvj (f08kjc) did not converge in 30 iterations (sweeps).
8:     pdaIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array a.
Constraints:
  • if order=Nag_ColMajor, pdamax1,m;
  • if order=Nag_RowMajor, pdamax1,n.
9:     sva[n]doubleOutput
On exit: the, possibly scaled, singular values of A.
If fail.errnum=0
The singular values of A are σi=αsva[i-1], for i=1,2,,n, where α is the scale factor stored in work[0]. Normally α=1, however, if some of the singular values of A might underflow or overflow, then α1 and the scale factor needs to be applied to obtain the singular values.
If fail.errnum>0
nag_dgesvj (f08kjc) did not converge in 30 iterations and α×sva may not be accurate.
10:   mvIntegerInput
On entry: if jobv=Nag_RightVecsMV, the product of Jacobi rotations is applied to the first mv rows of v.
If jobvNag_RightVecsMV, mv is ignored. See the description of jobv.
11:   v[dim]doubleInput/Output
Note: the dimension, dim, of the array v must be at least
  • max1,pdv×n when jobv=Nag_RightVecs;
  • max1,pdv×n when jobv=Nag_RightVecsMV and order=Nag_ColMajor;
  • max1,mv×pdv when jobv=Nag_RightVecsMV and order=Nag_RowMajor;
  • 1 otherwise.
The i,jth element of the matrix V is stored in
  • v[j-1×pdv+i-1] when order=Nag_ColMajor;
  • v[i-1×pdv+j-1] when order=Nag_RowMajor.
On entry: if jobv=Nag_RightVecsMV, v must contain an mv by n matrix to be premultiplied by the matrix V of right singular vectors.
On exit: the right singular vectors of A.
If jobv=Nag_RightVecs, v contains the n by n matrix of the right singular vectors.
If jobv=Nag_RightVecsMV, v contains the product of the computed right singular vector matrix and the initial matrix in the array v.
If jobv=Nag_NotRightVecs, v is not referenced.
12:   pdvIntegerInput
On entry: the stride separating row or column elements (depending on the value of order) in the array v.
Constraints:
  • if order=Nag_ColMajor,
    • if jobv=Nag_RightVecs, pdvmax1,n;
    • if jobv=Nag_RightVecsMV, pdvmax1,mv;
    • otherwise pdv1;
  • if order=Nag_RowMajor,
    • if jobv=Nag_RightVecs, pdvmax1,n;
    • if jobv=Nag_RightVecsMV, pdvmax1,n;
    • otherwise pdv1.
13:   work[lwork]doubleCommunication Array
On entry: if jobu=Nag_LeftVecsCtol, work[0]=ctol, where ctol defines the threshold for convergence. The process stops if all columns of A are mutually orthogonal up to ctol×ε. It is required that ctol1, i.e., it is not possible to force the function to obtain orthogonality below ε. ctol greater than 1/ε is meaningless, where ε is the machine precision.
On exit: contains information about the completed job.
work[0]
the scaling factor, α, such that σi=αsva[i-1], for i=1,2,,n are the computed singular values of A. (See description of sva.)
work[1]
nintwork[1]gives the number of the computed nonzero singular values.
work[2]
nintwork[2] gives the number of the computed singular values that are larger than the underflow threshold.
work[3]
nintwork[3] gives the number of iterations (sweeps of Jacobi rotations) needed for numerical convergence.
work[4]
maxijcosA:,i,A:,j in the last iteration (sweep). This is useful information in cases when nag_dgesvj (f08kjc) did not converge, as it can be used to estimate whether the output is still useful and for subsequent analysis.
work[5]
The largest absolute value over all sines of the Jacobi rotation angles in the last sweep. It can be useful for subsequent analysis.
Constraint: if jobu=Nag_LeftVecsCtol, work[0]1.0.
14:   lworkIntegerInput
On entry: the dimension of the array work.
Constraint: lworkmax6,m+n.
15:   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.
NE_BAD_PARAM
On entry, argument value had an illegal value.
NE_CONVERGENCE
nag_dgesvj (f08kjc) did not converge in the allowed number of iterations (30), but its output might still be useful.
NE_ENUM_INT_3
On entry, jobv=value, n=value, mv=value and pdv=value.
Constraint: if jobv=Nag_RightVecs, pdvmax1,n;
if jobv=Nag_RightVecsMV, pdvmax1,mv;
otherwise pdv1.
NE_ENUM_INT_4
On entry, jobv=value, pdv=value, n=value, mv=value and pdv=value.
Constraint: if jobv=Nag_RightVecs, pdvmax1,n;
if jobv=Nag_RightVecsMV, pdvmax1,n;
otherwise pdv1.
NE_ENUM_REAL_1
On entry, jobu=value and work[0]=value.
Constraint: if jobu=Nag_LeftVecsCtol, work[0]1.0.
NE_INT
On entry, m=value.
Constraint: m0.
On entry, pda=value.
Constraint: pda>0.
On entry, pdv=value.
Constraint: pdv>0.
NE_INT_2
On entry, m=value and n=value.
Constraint: mn0.
On entry, pda=value and m=value.
Constraint: pdamax1,m.
On entry, pda=value and n=value.
Constraint: pdamax1,n.
NE_INT_3
On entry, lwork=value, m=value and n=value.
Constraint: lworkmax6,m+n.
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

The computed singular value decomposition is nearly the exact singular value decomposition for a nearby matrix A+E , where
E2 = Oε A2 ,
and ε  is the machine precision. In addition, the computed singular vectors are nearly orthogonal to working precision. See Section 4.9 of Anderson et al. (1999) for further details.
See Section 6 of Drmac and Veselic (2008a) for a detailed discussion of the accuracy of the computed SVD.

8  Parallelism and Performance

nag_dgesvj (f08kjc) is not threaded by NAG in any implementation.
nag_dgesvj (f08kjc) 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 Users' Note for your implementation for any additional implementation-specific information.

9  Further Comments

This SVD algorithm is numerically superior to the bidiagonalization based QR algorithm implemented by nag_dgesvd (f08kbc) and the divide and conquer algorithm implemented by nag_dgesdd (f08kdc) algorithms and is considerably faster than previous implementations of the (equally accurate) Jacobi SVD method. Moreover, this algorithm can compute the SVD faster than nag_dgesvd (f08kbc) and not much slower than nag_dgesdd (f08kdc). See Section 3.3 of Drmac and Veselic (2008b) for the details.

10  Example

This example finds the singular values and left and right singular vectors of the 6 by 4 matrix
A = 2.27 -1.54 1.15 -1.94 0.28 -1.67 0.94 -0.78 -0.48 -3.09 0.99 -0.21 1.07 1.22 0.79 0.63 -2.35 2.93 -1.45 2.30 0.62 -7.39 1.03 -2.57 ,
together with approximate error bounds for the computed singular values and vectors.

10.1  Program Text

Program Text (f08kjce.c)

10.2  Program Data

Program Data (f08kjce.d)

10.3  Program Results

Program Results (f08kjce.r)


nag_dgesvj (f08kjc) (PDF version)
f08 Chapter Contents
f08 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2014