NAG Library Routine Document

1Purpose

f01blf calculates the rank and pseudo-inverse of an $m$ by $n$ real matrix, $m\ge n$, using a $QR$ factorization with column interchanges.

2Specification

Fortran Interface
 Subroutine f01blf ( m, n, t, a, lda, inc, d, u, ldu, du,
 Integer, Intent (In) :: m, n, lda, ldu Integer, Intent (Inout) :: ifail Integer, Intent (Out) :: irank, inc(n) Real (Kind=nag_wp), Intent (In) :: t Real (Kind=nag_wp), Intent (Inout) :: a(lda,n), u(ldu,n) Real (Kind=nag_wp), Intent (Out) :: aijmax(n), d(m), du(n)
#include nagmk26.h
 void f01blf_ (const Integer *m, const Integer *n, const double *t, double a[], const Integer *lda, double aijmax[], Integer *irank, Integer inc[], double d[], double u[], const Integer *ldu, double du[], Integer *ifail)

3Description

Householder's factorization with column interchanges is used in the decomposition $F=QU$, where $F$ is $A$ with its columns permuted, $Q$ is the first $r$ columns of an $m$ by $m$ orthogonal matrix and $U$ is an $r$ by $n$ upper-trapezoidal matrix of rank $r$. The pseudo-inverse of $F$ is given by $X$ where
 $X=UTUUT-1QT.$
If the matrix is found to be of maximum rank, $r=n$, $U$ is a nonsingular $n$ by $n$ upper-triangular matrix and the pseudo-inverse of $F$ simplifies to $X={U}^{-1}{Q}^{\mathrm{T}}$. The transpose of the pseudo-inverse of $A$ is overwritten on $A$.

4References

Peters G and Wilkinson J H (1970) The least squares problem and pseudo-inverses Comput. J. 13 309–316
Wilkinson J H and Reinsch C (1971) Handbook for Automatic Computation II, Linear Algebra Springer–Verlag

5Arguments

1:     $\mathbf{m}$ – IntegerInput
2:     $\mathbf{n}$ – IntegerInput
On entry: $m$ and $n$, the number of rows and columns in the matrix $A$.
Constraint: ${\mathbf{m}}\ge {\mathbf{n}}$.
3:     $\mathbf{t}$ – Real (Kind=nag_wp)Input
On entry: the tolerance used to decide when elements can be regarded as zero (see Section 9).
4:     $\mathbf{a}\left({\mathbf{lda}},{\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayInput/Output
On entry: the $m$ by $n$ rectangular matrix $A$.
On exit: the transpose of the pseudo-inverse of $A$.
5:     $\mathbf{lda}$ – IntegerInput
On entry: the first dimension of the array a as declared in the (sub)program from which f01blf is called.
Constraint: ${\mathbf{lda}}\ge {\mathbf{m}}$.
6:     $\mathbf{aijmax}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayOutput
On exit: ${\mathbf{aijmax}}\left(i\right)$ contains the element of largest modulus in the reduced matrix at the $i$th stage. If $r, then only the first $r+1$ elements of aijmax have values assigned to them; the remaining elements are unused. The ratio ${\mathbf{aijmax}}\left(1\right)/{\mathbf{aijmax}}\left(r\right)$ usually gives an indication of the condition number of the original matrix (see Section 9).
7:     $\mathbf{irank}$ – IntegerOutput
On exit: $r$, the rank of $A$ as determined using the tolerance t.
8:     $\mathbf{inc}\left({\mathbf{n}}\right)$ – Integer arrayOutput
On exit: the record of the column interchanges in the Householder factorization.
9:     $\mathbf{d}\left({\mathbf{m}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
10:   $\mathbf{u}\left({\mathbf{ldu}},{\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
11:   $\mathbf{ldu}$ – IntegerInput
On entry: the first dimension of the array u as declared in the (sub)program from which f01blf is called.
Constraint: ${\mathbf{ldu}}\ge {\mathbf{n}}$.
12:   $\mathbf{du}\left({\mathbf{n}}\right)$ – Real (Kind=nag_wp) arrayWorkspace
13:   $\mathbf{ifail}$ – IntegerInput/Output
On entry: ifail must be set to $0$, $-1\text{​ or ​}1$. If you are unfamiliar with this argument you should refer to Section 3.4 in How to Use the NAG Library and its Documentation for details.
For environments where it might be inappropriate to halt program execution when an error is detected, the value $-1\text{​ or ​}1$ is recommended. If the output of error messages is undesirable, then the value $1$ is recommended. Otherwise, if you are not familiar with this argument, the recommended value is $0$. When the value $-\mathbf{1}\text{​ or ​}\mathbf{1}$ is used it is essential to test the value of ifail on exit.
On exit: ${\mathbf{ifail}}={\mathbf{0}}$ unless the routine detects an error or a warning has been flagged (see Section 6).

6Error Indicators and Warnings

If on entry ${\mathbf{ifail}}=0$ or $-1$, explanatory error messages are output on the current error message unit (as defined by x04aaf).
Errors or warnings detected by the routine:
${\mathbf{ifail}}=1$
Inverse not found, due to an incorrect determination of irank (see Section 9).
${\mathbf{ifail}}=2$
Invalid tolerance, due to
 (i) t is negative, ${\mathbf{irank}}=-1$; (ii) t too large, ${\mathbf{irank}}=0$; (iii) t too small, ${\mathbf{irank}}>0$.
${\mathbf{ifail}}=3$
 On entry, ${\mathbf{m}}<{\mathbf{n}}$.
${\mathbf{ifail}}=-99$
See Section 3.9 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-399$
Your licence key may have expired or may not have been installed correctly.
See Section 3.8 in How to Use the NAG Library and its Documentation for further information.
${\mathbf{ifail}}=-999$
Dynamic memory allocation failed.
See Section 3.7 in How to Use the NAG Library and its Documentation for further information.

7Accuracy

For most matrices the pseudo-inverse is the best possible having regard to the condition of $A$ and the choice of t. Note that only the singular value decomposition method can be relied upon to give maximum accuracy for the precision of computation used and correct determination of the condition of a matrix (see Wilkinson and Reinsch (1971)).
The computed factors $Q$ and $U$ satisfy the relation $QU=F+E$ where
 $E2
in which $c$ is a modest function of $m$ and $n$, $\eta$ is the value of t, and $\epsilon$ is the machine precision.

8Parallelism and Performance

f01blf is not threaded in any implementation.

The time taken by f01blf is approximately proportional to $mnr$.
The most difficult practical problem is the determination of the rank of the matrix (see pages 314–315 of Peters and Wilkinson (1970)); only the singular value decomposition method gives a reliable indication of rank deficiency (see pages 134–151 of Wilkinson and Reinsch (1971) and f08kbf (dgesvd)). In f01blf a tolerance, t, is used to recognize ‘zero’ elements in the remaining matrix at each step in the factorization. The value of t should be set at $n$ times the bound on possible errors in individual elements of the original matrix. If the elements of $A$ vary widely in their orders of magnitude, of course this presents severe difficulties. Sound decisions can only be made by somebody who appreciates the underlying physical problem.
If the condition number of $A$ is ${10}^{p}$ we expect to get $p$ figures wrong in the pseudo-inverse. An estimate of the condition number is usually given by ${\mathbf{aijmax}}\left(1\right)/{\mathbf{aijmax}}\left(r\right)$.

10Example

A complete program follows which outputs the maximum of the moduli of the ‘remaining’ elements at each step in the factorization, the rank, as determined by the given value of t, and the transposed pseudo-inverse. Data and results are given for an example which is a $6$ by $5$ matrix of deficient rank in which the last column is a linear combination of the other four. Setting t to $\epsilon$ times the norm of the matrix, the rank is correctly determined as $4$ and the pseudo-inverse is computed to full implementation accuracy.

10.1Program Text

Program Text (f01blfe.f90)

10.2Program Data

Program Data (f01blfe.d)

10.3Program Results

Program Results (f01blfe.r)

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