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_eigen_withdraw_real_gen_qu_svd (f02wd)

▸▿ Contents

1 Purpose

2 Syntax

3 Description

4 References

▸▿ 5 Parameters

5.1 Compulsory Input Parameters

5.2 Optional Input Parameters

5.3 Output Parameters

6 Error Indicators and Warnings

7 Accuracy

▸▿ 8 Further Comments

8.1 Timing

8.2 General Remarks

8.3 Determining the Rank of A

8.4 Storage Details of the QU Factorization

9 Example

Purpose

nag_eigen_real_gen_qu_svd (f02wd) returns the Householder

Q U

factorization of a real rectangular

m

n

(m \geq n)

matrix

A

. Further, on request or if

A

is not of full rank, part or all of the singular value decomposition of

A

is returned.

Note: this function is scheduled to be withdrawn, please see f02wd in Advice on Replacement Calls for Withdrawn/Superseded Routines..

Syntax

[a, b, svd, irank, z, sv, r, pt, work, ifail] = f02wd(a, wantb, b, tol, svd, wantr, wantpt, lwork, 'm', m, 'n', n)

[a, b, svd, irank, z, sv, r, pt, work, ifail] = nag_eigen_withdraw_real_gen_qu_svd(a, wantb, b, tol, svd, wantr, wantpt, lwork, 'm', m, 'n', n)

Description

The real

m

n

(m \geq n)

matrix

A

is first factorized as

A = Q (\begin{array}{l} U \\ 0 \end{array}),

where

Q

is an

m

m

orthogonal matrix and

U

is an

n

n

upper triangular matrix.

If either

U

is singular or svd is supplied as true, then the singular value decomposition (SVD) of

U

is obtained so that

U

is factorized as

U = R D P^{T},

where

R

and

P

are

n

n

orthogonal matrices and

D

is the

n

n

diagonal matrix

D = diag (s v_{1}, s v_{2}, \dots, s v_{n}),

with

s v_{1} \geq s v_{2} \geq \dots \geq s v_{n} \geq 0 .

Note that the SVD of

A

is then given by

A = Q_{1} (\begin{array}{l} D \\ 0 \end{array}) P^{T} where Q_{1} = Q (\begin{array}{l} R & 0 \\ 0 & I \end{array}),

the diagonal elements of

D

being the singular values of

A

The option to form a vector

Q^{T} b

, or if appropriate

Q_{1}^{T} b

, is also provided.

The rank of the matrix

A

, based upon a user-supplied argument tol, is also returned.

The

Q U

factorization of

A

is obtained by Householder transformations. To obtain the SVD of

U

the matrix is first reduced to bidiagonal form by means of plane rotations and then the

Q R

algorithm is used to obtain the SVD of the bidiagonal form.

References

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

Parameters

Compulsory Input Parameters

1: $a (lda, n)$ – double array: lda, the first dimension of the array, must satisfy the constraint $lda \geq m$ .
The leading $m$ by $n$ part of a must contain the matrix to be factorized.
2: $wantb$ – logical scalar: Must be true if $Q^{T} b$ or $Q_{1}^{T} b$ is required.
If on entry $wantb = false$ , b is not referenced.
3: $b (m)$ – double array: If wantb is supplied as true, b must contain the $m$ element vector $b$ . Otherwise, b is not referenced.
4: $tol$ – double scalar: Must specify a relative tolerance to be used to determine the rank of $A$ . tol should be chosen as approximately the largest relative error in the elements of $A$ . For example, if the elements of $A$ are correct to about $4$ significant figures, tol should be set to about $5 \times 10^{- 4}$ . See Determining the Rank of for a description of how tol is used to determine rank.
If tol is outside the range $(ε, 1.0)$ , where $ε$ is the machine precision, the value $ε$ is used in place of tol. For most problems this is unreasonably small.
5: $svd$ – logical scalar: Must be true if the singular values are to be found even if $A$ is of full rank.
If before entry, $svd = false$ and $A$ is determined to be of full rank, only the $Q U$ factorization of $A$ is computed.
6: $wantr$ – logical scalar: Must be true if the orthogonal matrix $R$ is required when the singular values are computed.
If on entry $wantr = false$ , r is not referenced.
7: $wantpt$ – logical scalar: Must be true if the orthogonal matrix $P^{T}$ is required when the singular values are computed.
Note that if svd is returned as true, pt is referenced even if wantpt is supplied as false, but see argument pt.
8: $lwork$ – int64int32nag_int scalar: The dimension of the array work.

Constraint: $lwork \geq 3 \times n$ .

Optional Input Parameters

1: $m$ – int64int32nag_int scalar: Default: the dimension of the array b and the first dimension of the array a. (An error is raised if these dimensions are not equal.)
$m$ , the number of rows of the matrix $A$ .

Constraint: $m \geq n$ .
2: $n$ – int64int32nag_int scalar: Default: the second dimension of the array a.
$n$ , the number of columns of the matrix $A$ .

Constraint: $1 \leq n \leq m$ .

Output Parameters

1: $a (lda, n)$ – double array

The leading

m

n

part of a, together with the

n

-element vector z, contains details of the Householder

Q U

factorization.

Details of the storage of the

Q U

factorization are given in Storage Details of the Factorization.

2: $b (m)$ – double array

Contains

Q_{1}^{T} b

if svd is returned as true and

Q^{T} b

if svd is returned as false.

3: $svd$ – logical scalar

Is returned as false if only the

Q U

factorization of

A

has been obtained and is returned as true if the singular values of

A

have been obtained.

4: $irank$ – int64int32nag_int scalar

Returns the rank of the matrix

A

. (It should be noted that it is possible for irank to be returned as

n

and svd to be returned as true, even if svd was supplied as false. This means that the matrix

U

only just failed the test for nonsingularity.)

5: $z (n)$ – double array

The

n

-element vector z contains some details of the Householder transformations. See Storage Details of the Factorization for further information.

6: $sv (n)$ – double array

If svd is returned as true, sv contains the

n

singular values of

A

arranged in descending order.

7: $r (ldr, n)$ – double array

The first dimension,

ldr

, of the array r will be

if $wantr = true$ , $ldr = n$ ;
otherwise $ldr = 1$ .

The second dimension of the array r will be

n

wantr = true

and

1

otherwise.

If svd is returned as true and wantr was supplied as true, the leading

n

n

part of r will contain the left-hand orthogonal matrix of the svd of

U

8: $pt (ldpt, n)$ – double array

If svd is returned as true and wantpt was supplied as true, the leading

n

n

part of pt contains the orthogonal matrix

P^{T}

If svd is returned as true, but wantpt was supplied as false, the leading

n

n

part of pt is used for internal workspace.

9: $work (lwork)$ – double array

If svd is returned as false,

work (1)

contains the condition number

{‖U‖}_{E} {‖U^{- 1}‖}_{E}

of the upper triangular matrix

U

If svd is returned as true,

work (1)

will contain the total number of iterations taken by the

Q R

algorithm.

The rest of the array is used as workspace and so contains no meaningful information.

10: $ifail$ – int64int32nag_int scalar

ifail = 0

unless the function detects an error (see Error Indicators and Warnings).

Error Indicators and Warnings

Errors or warnings detected by the function:

$ifail = 1$

On entry,	$n < 1$ ,
or	$m < n$ ,
or	$lda < m$ ,
or	$ldr < n$ when $wantr = true$ ,
or	$ldpt < n$
or	$lwork < 3 \times n$ .

(The function only checks ldr if wantr is supplied as true.)

$ifail > 1$: The $Q R$ algorithm has failed to converge to the singular values in $50 \times n$ iterations. In this case $sv (1), sv (2), \dots, sv (ifail - 1)$ may not have been correctly found and the remaining singular values may not be the smallest singular values. The matrix $A$ has nevertheless been factorized as $A = Q_{1} C P^{T}$ , where $C$ is an upper bidiagonal matrix with $sv (1), sv (2), \dots, sv (n)$ as its diagonal elements and $work (2), work (3), \dots, work (n)$ as its superdiagonal elements.

This failure cannot occur if svd is returned as false and in any case is extremely rare.

$ifail = - 99$: An unexpected error has been triggered by this routine. Please contact NAG.

$ifail = - 399$: Your licence key may have expired or may not have been installed correctly.

$ifail = - 999$: Dynamic memory allocation failed.

Accuracy

The computed factors

Q

U

R

D

and

P^{T}

satisfy the relations

Q (\begin{array}{l} U \\ 0 \end{array}) = A + E,

Q (\begin{array}{l} R & 0 \\ 0 & I \end{array}) (\begin{array}{l} D \\ 0 \end{array}) P^{T} = A + F

where

{‖E‖}_{2} \leq c_{1} ε {‖A‖}_{2}

{‖F‖}_{2} \leq c_{2} ε {‖A‖}_{2}

ε

being the machine precision and

c_{1}

and

c_{2}

are modest functions of

m

and

n

. Note that

{‖A‖}_{2} = s v_{1}

Further Comments

Timing

The time taken by nag_eigen_real_gen_qu_svd (f02wd) to obtain the Householder

Q U

factorization is approximately proportional to

n^{2} (3 m - n)

The additional time taken to obtain the singular value decomposition is approximately proportional to

n^{3}

, where the constant of proportionality depends upon whether or not the orthogonal matrices

R

and

P^{T}

are required.

General Remarks

Singular vectors associated with a zero or multiple singular value, are not uniquely determined, even in exact arithmetic, and very different results may be obtained if they are computed on different machines.

This function is called by the least squares function nag_linsys_real_gen_solve (f04jg).

Determining the Rank of A

Following the

Q U

factorization of

A

, if svd is supplied as false, then the condition number of

U

given by

C (U) = {‖U‖}_{F} {‖U^{- 1}‖}_{F}

is found, where

{‖.‖}_{F}

denotes the Frobenius norm, and if

C (U)

is such that

C (U) \times tol > 1.0

then

U

is regarded as singular and the singular values of

A

are computed. If this test is not satisfied, then the rank of

A

is set to

n

. Note that if svd is supplied as true then this test is omitted.

When the singular values are computed, then the rank of

A

r

, is returned as the largest integer such that

s v_{r} > tol \times s v_{1},

unless

s v_{1} = 0

in which case

r

is returned as zero. That is, singular values which satisfy

s v_{i} \leq tol \times s v_{1}

are regarded as negligible because relative perturbations of order tol can make such singular values zero.

Storage Details of the QU Factorization

The

k

th Householder transformation matrix,

T_{k}

, used in the

Q U

factorization is chosen to introduce the zeros into the

k

th column and has the form

T_{k} = I - 2 (\begin{matrix} 0 \\ u \end{matrix}) (\begin{matrix} 0 & u^{T} \end{matrix}), u^{T} u = 1,

where

u

is an

(m - k + 1)

element vector.

In place of

u

the function actually computes the vector

z

given by

z = 2 u_{1} u .

The first element of

z

is stored in

z (k)

and the remaining elements of

z

are overwritten on the subdiagonal elements of the

k

th column of a. The upper triangular matrix

U

is overwritten on the

n

n

upper triangular part of a.

Example

This example obtains the rank and the singular value decomposition of the

6

4

matrix

A

given by

A = (\begin{array}{r} 22.25 & 31.75 & - 38.25 & 65.50 \\ 20.00 & 26.75 & 28.50 & - 26.50 \\ - 15.25 & 24.25 & 27.75 & 18.50 \\ 27.25 & 10.00 & 3.00 & 2.00 \\ - 17.25 & - 30.75 & 11.25 & 7.50 \\ 17.25 & 30.75 & - 11.25 & - 7.50 \end{array})

the value tol to be taken as

5 \times 10^{- 4}

Open in the MATLAB editor: f02wd_example

function f02wd_example


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

a = [ 22.25, 31.75,-38.25, 65.5;
      20.00, 26.75, 28.50,-26.5;
     -15.25, 24.25, 27.75, 18.5;
      27.25, 10.00,  3.00, 2.00;
     -17.25,-30.75, 11.25, 7.50;
      17.25, 30.75,-11.25,-7.50];

% Compute rank and SVD of A
wantb = false;
b     = zeros(6,1);
tol   = 0.0005;
svd   = true;
wantr = true;
wantpt = true;
lwork = int64(24);

[a, b, svd, irank, z, sv, r, pt, work, ifail] = ...
f02wd( ...
       a, wantb, b, tol, svd, wantr, wantpt, lwork);

fprintf('Rank of A is %2d\n\n', irank);
disp('Details of QU factorization');
disp(a);

disp('Vector z');
disp(z');

disp('Matrix R');
disp(r);

disp('Singular values');
disp(sv');

disp('Matrix P');
disp(pt');

f02wd example results

Rank of A is  4

Details of QU factorization
  -49.6519  -44.4092   20.3542   -8.8818
    0.4028  -48.2767   -9.5887  -20.3761
   -0.3071    0.8369   52.9270  -48.8806
    0.5488   -0.3907   -0.8364  -50.6742
   -0.3474   -0.2585   -0.1851    0.6321
    0.3474    0.2585    0.1851   -0.6321

Vector z
    1.4481    1.1153    1.4817    1.4482

Matrix R
   -0.5639    0.6344    0.4229    0.3172
   -0.3512    0.3951   -0.6791   -0.5093
   -0.6403   -0.5692    0.3095   -0.4126
   -0.3855   -0.3427   -0.5140    0.6854

Singular values
   91.0000   68.2500   45.5000   22.7500

Matrix P
    0.3077   -0.4615   -0.4615   -0.6923
    0.4615   -0.6923    0.3077    0.4615
   -0.4615   -0.3077    0.6923   -0.4615
    0.6923    0.4615    0.4615   -0.3077

PDF version (NAG web site, 64-bit version, 64-bit version)

Chapter Contents

Chapter Introduction

NAG Toolbox