hide long namesshow long names
hide short namesshow short names
Integer type:  int32  int64  nag_int  show int32  show int32  show int64  show int64  show nag_int  show nag_int

PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

NAG Toolbox: nag_lapack_dgesvj (f08kj)

Purpose

nag_lapack_dgesvj (f08kj) computes the one-sided Jacobi singular value decomposition (SVD) of a real mm by nn matrix AA, mnmn, with fast scaled rotations and de Rijk’s pivoting, optionally computing the left and/or right singular vectors. For m < nm<n, the functions nag_lapack_dgesvd (f08kb) or nag_lapack_dgesdd (f08kd) may be used.

Syntax

[a, sva, v, work, info] = f08kj(joba, jobu, jobv, a, mv, v, work, 'm', m, 'n', n)
[a, sva, v, work, info] = nag_lapack_dgesvj(joba, jobu, jobv, a, mv, v, work, 'm', m, 'n', n)

Description

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

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

Parameters

Compulsory Input Parameters

1:     joba – string (length ≥ 1)
Specifies the structure of matrix AA.
joba = 'L'joba='L'
The input matrix AA is lower triangular.
joba = 'U'joba='U'
The input matrix AA is upper triangular.
joba = 'G'joba='G'
The input matrix AA is a general mm by nn matrix, mnmn.
Constraint: joba = 'L'joba='L', 'U''U' or 'G''G'.
2:     jobu – string (length ≥ 1)
Specifies whether to compute the left singular vectors and if so whether you want to control their numerical orthogonality threshold.
jobu = 'U'jobu='U'
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 × εtol=ctol×ε, where εε is the machine precision and ctol = sqrt(m)ctol=m.
jobu = 'C'jobu='C'
Analogous to jobu = 'U'jobu='U', except that you can control the level of numerical orthogonality of the computed left singular vectors. The orthogonality threshold is set to tol = ctol × εtol=ctol×ε, where ctolctol is given on input in work(1)work1. The option jobu = 'C'jobu='C' can be used if m × εm×ε is a satisfactory orthogonality of the computed left singular vectors, so ctol = mctol=m could save a few sweeps of Jacobi rotations. See the descriptions of a and work(1)work1.
jobu = 'N'jobu='N'
The matrix UU is not computed. However, see the description of a.
Constraint: jobu = 'U'jobu='U', 'C''C' or 'N''N'.
3:     jobv – string (length ≥ 1)
Specifies whether and how to compute the right singular vectors.
jobv = 'V'jobv='V'
The matrix VV is computed and returned in the array v.
jobv = 'A'jobv='A'
The Jacobi rotations are applied to the leading mvmv by nn part of the array v. In other words, the right singular vector matrix VV is not computed explicitly, instead it is applied to an mvmv by nn matrix initially stored in the first mv rows of v.
jobv = 'N'jobv='N'
The matrix VV is not computed and the array v is not referenced.
Constraint: jobv = 'V'jobv='V', 'A''A' or 'N''N'.
4:     a(lda, : :) – double array
The first dimension of the array a must be at least max (1,m)max(1,m)
The second dimension of the array must be at least max (1,n)max(1,n)
The mm by nn matrix AA.
5:     mv – int64int32nag_int scalar
If jobv = 'A'jobv='A', the product of Jacobi rotations is applied to the first mvmv rows of v.
If jobv'A'jobv'A', mv is ignored. See the description of jobv.
6:     v(ldv, : :) – double array
The first dimension, ldv, of the array v must satisfy
  • if jobv = 'V'jobv='V', ldvmax (1,n)ldvmax(1,n);
  • if jobv = 'A'jobv='A', ldvmax (1,mv)ldvmax(1,mv);
  • otherwise ldv1ldv1.
The second dimension of the array must be at least max (1,n)max(1,n) if jobv = 'V'jobv='V' or 'A''A', and at least 11 otherwise
If jobv = 'A'jobv='A', v must contain an mvmv by nn matrix to be premultiplied by the matrix VV of right singular vectors.
7:     work(lwork) – double array
lwork, the dimension of the array, must satisfy the constraint lworkmax (6,m + n)lworkmax(6,m+n).
If jobu = 'C'jobu='C', work(1) = ctolwork1=ctol, where ctolctol defines the threshold for convergence. The process stops if all columns of AA are mutually orthogonal up to ctol × εctol×ε. It is required that ctol1ctol1, i.e., it is not possible to force the function to obtain orthogonality below εε. ctolctol greater than 1 / ε1/ε is meaningless, where εε is the machine precision.
Constraint: if jobu = 'C'jobu='C', work(1)1.0work11.0.

Optional Input Parameters

1:     m – int64int32nag_int scalar
Default: The first dimension of the array a.
mm, the number of rows of the matrix AA.
Constraint: m0m0.
2:     n – int64int32nag_int scalar
Default: The second dimension of the array a.
nn, the number of columns of the matrix AA.
Constraint: mn0mn0.

Input Parameters Omitted from the MATLAB Interface

lda ldv lwork

Output Parameters

1:     a(lda, : :) – double array
The first dimension of the array a will be max (1,m)max(1,m)
The second dimension of the array will be max (1,n)max(1,n)
ldamax (1,m)ldamax(1,m).
The matrix UU containing the left singular vectors of AA.
If jobu = 'U'jobu='U' or 'C''C'
if info = 0info=0
rank(A)rank(A) orthonormal columns of UU are returned in the leading rank(A)rank(A) columns of the array a. Here rank(A)nrank(A)n is the number of computed singular values of AA that are above the safe range parameter, as returned by nag_machine_real_safe (x02am). The singular vectors corresponding to underflowed or zero singular values are not computed. The value of rank(A)rank(A) is returned by rounding work(2)work2 to the nearest whole number. Also see the descriptions of sva and work. The computed columns of UU are mutually numerically orthogonal up to approximately tol = sqrt(m) × εtol=m×ε; or tol = ctol × εtol=ctol×ε (jobu = 'C'jobu='C'), where εε is the machine precision and ctolctol is supplied on entry in work(1)work1, see the description of jobu.
If info > 0info>0
nag_lapack_dgesvj (f08kj) did not converge in 3030 iterations (sweeps). In this case, the computed columns of UU may not be orthogonal up to toltol. The output UU (stored in a), ΣΣ (given by the computed singular values in sva) and VV is still a decomposition of the input matrix AA in the sense that the residual Aα × U × Σ × VT2 / A2A-α×U×Σ×VT2/A2 is small, where αα is the value returned in work(1)work1.
If jobu = 'N'jobu='N'
if info = 0info=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 UU is not an issue and iterations are stopped when the columns of the iterated matrix are numerically orthogonal up to approximately m × εm×ε. Thus, on exit, a contains the columns of UU scaled with the corresponding singular values.
If info > 0info>0
nag_lapack_dgesvj (f08kj) did not converge in 3030 iterations (sweeps).
2:     sva(n) – double array
The, possibly scaled, singular values of AA.
If info = 0info=0
The singular values of AA are σi = αsva(i)σi=αsvai, for i = 1,2,,ni=1,2,,n, where αα is the scale factor stored in work(1)work1. Normally α = 1α=1, however, if some of the singular values of AA might underflow or overflow, then α1α1 and the scale factor needs to be applied to obtain the singular values.
If info > 0info>0
nag_lapack_dgesvj (f08kj) did not converge in 3030 iterations and α × svaα×sva may not be accurate.
3:     v(ldv, : :) – double array
The first dimension, ldv, of the array v will be
  • if jobv = 'V'jobv='V', ldvmax (1,n)ldvmax(1,n);
  • if jobv = 'A'jobv='A', ldvmax (1,mv)ldvmax(1,mv);
  • otherwise ldv1ldv1.
The second dimension of the array will be max (1,n)max(1,n) if jobv = 'V'jobv='V' or 'A''A', and at least 11 otherwise
The right singular vectors of AA.
If jobv = 'V'jobv='V', v contains the nn by nn matrix of the right singular vectors.
If jobv = 'A'jobv='A', v contains the product of the computed right singular vector matrix and the initial matrix in the array v.
If jobv = 'N'jobv='N', v is not referenced.
4:     work(lwork) – double array
lworkmax (6,m + n)lworkmax(6,m+n).
Contains information about the completed job.
work(1)work1
the scaling factor, αα, such that σi = αsva(i)σi=αsvai, for i = 1,2,,ni=1,2,,n are the computed singular values of AA. (See description of sva.)
work(2)work2
nint(work(2))nint(work2)gives the number of the computed nonzero singular values.
work(3)work3
nint(work(3))nint(work3) gives the number of the computed singular values that are larger than the underflow threshold.
work(4)work4
nint(work(4))nint(work4) gives the number of iterations (sweeps of Jacobi rotations) needed for numerical convergence.
work(5)work5
maxij|cos(A( : ,i),A( : ,j))|maxij|cos(A(:,i),A(:,j))| in the last iteration (sweep). This is useful information in cases when nag_lapack_dgesvj (f08kj) did not converge, as it can be used to estimate whether the output is still useful and for subsequent analysis.
work(6)work6
The largest absolute value over all sines of the Jacobi rotation angles in the last sweep. It can be useful for subsequent analysis.
5:     info – int64int32nag_int scalar
info = 0info=0 unless the function detects an error (see Section [Error Indicators and Warnings]).

Error Indicators and Warnings

Cases prefixed with W are classified as warnings and do not generate an error of type NAG:error_n. See nag_issue_warnings.

W INFO > 0INFO>0
nag_lapack_dgesvj (f08kj) did not converge in the allowed number of iterations (3030), but its output might still be useful.

Accuracy

The computed singular value decomposition is nearly the exact singular value decomposition for a nearby matrix (A + E) (A+E) , where
E2 = O(ε) A2 ,
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.

Further Comments

This SVD algorithm is numerically superior to the bidiagonalization based QRQR algorithm implemented by nag_lapack_dgesvd (f08kb) and the divide and conquer algorithm implemented by nag_lapack_dgesdd (f08kd) 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_lapack_dgesvd (f08kb) and not much slower than nag_lapack_dgesdd (f08kd). See Section 3.3 of Drmac and Veselic (2008b) for the details.

Example

function nag_lapack_dgesvj_example
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];
joba = 'g';
jobu = 'u';
jobv = 'v';
work = zeros(10,1);
v    = zeros(4, 4);
mv = int64(0);
% Compute the singular values and left and right singular vectors
% of A (A = U*S*V, m >= n)
[a, sva, v, work, info] = nag_lapack_dgesvj(joba, jobu, jobv, a, mv, v, work);

if info == 0
  % Compute the approximate error bound for the computed singular values
  % using the 2-norm, s(1) = norm(A), and machine precision, eps.
  eps = nag_machine_precision;
  serrbd = eps*sva(1);

  % Print solution
  fprintf('\nSingular values:\n');
  disp(transpose(sva));
  if (abs(work(1)-1) > eps)
    fprintf('\nValues nned scaling by %13.5e.\n', work(1));
  end

  fprintf('\n');
  [ifail] = nag_file_print_matrix_real_gen('g', ' ', a, 'Left singular vectors');
  fprintf('\n');
  [ifail] = nag_file_print_matrix_real_gen('g', ' ', v, 'Right singular vectors');

  % Call nag_lapack_ddisna to estimate reciprocal condition numbers for the singular vectors
  [rcondu, info] = nag_lapack_ddisna('Left', int64(6), int64(4), sva);
  [rcondv, info] = nag_lapack_ddisna('Right', int64(6), int64(4), sva);

  % Print the approximate error bounds for the singular values and vectors
  fprintf('\nError estimate for the singular values a\n');
  fprintf('%11.1e\n', serrbd);
  fprintf('\nError estimates for left singular vectors\n');
  fprintf('%11.1e ',serrbd./rcondu);
  fprintf('\n\nError estimates for right singular vectors\n');
  fprintf('%11.1e ',serrbd./rcondv);
  fprintf('\n');
end
 

Singular values:
    9.9966    3.6831    1.3569    0.5000


 Left singular vectors
          1       2       3       4
 1  -0.2774  0.6003 -0.1277  0.1323
 2  -0.2020  0.0301  0.2805  0.7034
 3  -0.2918 -0.3348  0.6453  0.1906
 4   0.0938  0.3699  0.6781 -0.5399
 5   0.4213 -0.5266  0.0413 -0.0575
 6  -0.7816 -0.3353 -0.1645 -0.3957

 Right singular vectors
          1       2       3       4
 1  -0.1921  0.8030  0.0041 -0.5642
 2   0.8794  0.3926 -0.0752  0.2587
 3  -0.2140  0.2980  0.7827  0.5027
 4   0.3795 -0.3351  0.6178 -0.6017

Error estimate for the singular values a
    1.1e-15

Error estimates for left singular vectors
    1.8e-16     4.8e-16     1.3e-15     2.2e-15 

Error estimates for right singular vectors
    1.8e-16     4.8e-16     1.3e-15     1.3e-15 

function f08kj_example
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];
joba = 'g';
jobu = 'u';
jobv = 'v';
work = zeros(10,1);
v    = zeros(4, 4);
mv = int64(0);
% Compute the singular values and left and right singular vectors
% of A (A = U*S*V, m >= n)
[a, sva, v, work, info] = f08kj(joba, jobu, jobv, a, mv, v, work);

if info == 0
  % Compute the approximate error bound for the computed singular values
  % using the 2-norm, s(1) = norm(A), and machine precision, eps.
  eps = x02aj;
  serrbd = eps*sva(1);

  % Print solution
  fprintf('\nSingular values:\n');
  disp(transpose(sva));
  if (abs(work(1)-1) > eps)
    fprintf('\nValues nned scaling by %13.5e.\n', work(1));
  end

  fprintf('\n');
  [ifail] = x04ca('g', ' ', a, 'Left singular vectors');
  fprintf('\n');
  [ifail] = x04ca('g', ' ', v, 'Right singular vectors');

  % Call f08fl to estimate reciprocal condition numbers for the singular vectors
  [rcondu, info] = f08fl('Left', int64(6), int64(4), sva);
  [rcondv, info] = f08fl('Right', int64(6), int64(4), sva);

  % Print the approximate error bounds for the singular values and vectors
  fprintf('\nError estimate for the singular values a\n');
  fprintf('%11.1e\n', serrbd);
  fprintf('\nError estimates for left singular vectors\n');
  fprintf('%11.1e ',serrbd./rcondu);
  fprintf('\n\nError estimates for right singular vectors\n');
  fprintf('%11.1e ',serrbd./rcondv);
  fprintf('\n');
end
 

Singular values:
    9.9966    3.6831    1.3569    0.5000


 Left singular vectors
          1       2       3       4
 1  -0.2774  0.6003 -0.1277  0.1323
 2  -0.2020  0.0301  0.2805  0.7034
 3  -0.2918 -0.3348  0.6453  0.1906
 4   0.0938  0.3699  0.6781 -0.5399
 5   0.4213 -0.5266  0.0413 -0.0575
 6  -0.7816 -0.3353 -0.1645 -0.3957

 Right singular vectors
          1       2       3       4
 1  -0.1921  0.8030  0.0041 -0.5642
 2   0.8794  0.3926 -0.0752  0.2587
 3  -0.2140  0.2980  0.7827  0.5027
 4   0.3795 -0.3351  0.6178 -0.6017

Error estimate for the singular values a
    1.1e-15

Error estimates for left singular vectors
    1.8e-16     4.8e-16     1.3e-15     2.2e-15 

Error estimates for right singular vectors
    1.8e-16     4.8e-16     1.3e-15     1.3e-15 


PDF version (NAG web site, 64-bit version, 64-bit version)
Chapter Contents
Chapter Introduction
NAG Toolbox

© The Numerical Algorithms Group Ltd, Oxford, UK. 2009–2013