NAG Library Routine Document

F08BEF (DGEQPF)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

F08BEF (DGEQPF) computes the

Q R

factorization, with column pivoting, of a real

m

n

matrix.

2 Specification

SUBROUTINE F08BEF (

M, N, A, LDA, JPVT, TAU, WORK, INFO)

INTEGER	M, N, LDA, JPVT(*), INFO
REAL (KIND=nag_wp)	A(LDA,), TAU(min(M,N)), WORK(3N)

The routine may be called by its LAPACK name dgeqpf.

3 Description

F08BEF (DGEQPF) forms the

Q R

factorization, with column pivoting, of an arbitrary rectangular real

m

n

matrix.

m \geq n

, the factorization is given by:

A P = Q (\begin{array}{r} R \\ 0 \end{array}),

where

R

is an

n

n

upper triangular matrix,

Q

is an

m

m

orthogonal matrix and

P

is an

n

n

permutation matrix. It is sometimes more convenient to write the factorization as

A P = (\begin{array}{r} Q_{1} & Q_{2} \end{array}) (\begin{array}{r} R \\ 0 \end{array}),

which reduces to

A P = Q_{1} R,

where

Q_{1}

consists of the first

n

columns of

Q

, and

Q_{2}

the remaining

m - n

columns.

m < n

R

is trapezoidal, and the factorization can be written

A P = Q (\begin{array}{r} R_{1} & R_{2} \end{array}),

where

R_{1}

is upper triangular and

R_{2}

is rectangular.

The matrix

Q

is not formed explicitly but is represented as a product of

\min (m, n)

elementary reflectors (see the F08 Chapter Introduction for details). Routines are provided to work with

Q

in this representation (see Section 8).

Note also that for any

k < n

, the information returned in the first

k

columns of the array A represents a

Q R

factorization of the first

k

columns of the permuted matrix

A P

The routine allows specified columns of

A

to be moved to the leading columns of

A P

at the start of the factorization and fixed there. The remaining columns are free to be interchanged so that at the

i

th stage the pivot column is chosen to be the column which maximizes the

2

-norm of elements

i

m

over columns

i

n

4 References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

5 Parameters

1: M – INTEGERInput: On entry: $m$ , the number of rows of the matrix $A$ .
Constraint: $M \geq 0$ .
2: N – INTEGERInput: On entry: $n$ , the number of columns of the matrix $A$ .
Constraint: $N \geq 0$ .
3: A(LDA, $*$ ) – REAL (KIND=nag_wp) arrayInput/Output: Note: the second dimension of the array A must be at least $\max (1, N)$ .
On entry: the $m$ by $n$ matrix $A$ .

On exit: if $m \geq n$ , the elements below the diagonal are overwritten by details of the orthogonal matrix $Q$ and the upper triangle is overwritten by the corresponding elements of the $n$ by $n$ upper triangular matrix $R$ .
If $m < n$ , the strictly lower triangular part is overwritten by details of the orthogonal matrix $Q$ and the remaining elements are overwritten by the corresponding elements of the $m$ by $n$ upper trapezoidal matrix $R$ .
4: LDA – INTEGERInput: On entry: the first dimension of the array A as declared in the (sub)program from which F08BEF (DGEQPF) is called.
Constraint: $LDA \geq \max (1, M)$ .
5: JPVT( $*$ ) – INTEGER arrayInput/Output: Note: the dimension of the array JPVT must be at least $\max (1, N)$ .
On entry: if $JPVT (i) \neq 0$ , then the $i$ th column of $A$ is moved to the beginning of $A P$ before the decomposition is computed and is fixed in place during the computation. Otherwise, the $i$ th column of $A$ is a free column (i.e., one which may be interchanged during the computation with any other free column).

On exit: details of the permutation matrix $P$ . More precisely, if $JPVT (i) = k$ , then the $k$ th column of $A$ is moved to become the $i$ th column of $A P$ ; in other words, the columns of $A P$ are the columns of $A$ in the order $JPVT (1), JPVT (2), \dots, JPVT (n)$ .
6: TAU( $\min (M, N)$ ) – REAL (KIND=nag_wp) arrayOutput: On exit: further details of the orthogonal matrix $Q$ .
7: WORK( $3 \times N$ ) – REAL (KIND=nag_wp) arrayWorkspace
8: INFO – INTEGEROutput: On exit: $INFO = 0$ unless the routine detects an error (see Section 6).

6 Error Indicators and Warnings

Errors or warnings detected by the routine:

$INFO < 0$: If $INFO = - i$ , argument $i$ had an illegal value. An explanatory message is output, and execution of the program is terminated.

7 Accuracy

The computed factorization is the exact factorization of a nearby matrix

(A + E)

, where

{‖E‖}_{2} = O (ε) {‖A‖}_{2},

and

ε

is the machine precision.

8 Further Comments

The total number of floating point operations is approximately

\frac{2}{3} n^{2} (3 m - n)

m \geq n

\frac{2}{3} m^{2} (3 n - m)

m < n

To form the orthogonal matrix

Q

F08BEF (DGEQPF) may be followed by a call to F08AFF (DORGQR):

CALL DORGQR(M,M,MIN(M,N),A,LDA,TAU,WORK,LWORK,INFO)

but note that the second dimension of the array A must be at least M, which may be larger than was required by F08BEF (DGEQPF).

When

m \geq n

, it is often only the first

n

columns of

Q

that are required, and they may be formed by the call:

CALL DORGQR(M,N,N,A,LDA,TAU,WORK,LWORK,INFO)

To apply

Q

to an arbitrary real rectangular matrix

C

, F08BEF (DGEQPF) may be followed by a call to F08AGF (DORMQR). For example,

CALL DORMQR('Left','Transpose',M,P,MIN(M,N),A,LDA,TAU,C,LDC,WORK, &
              LWORK,INFO)

forms

C = Q^{T} C

, where

C

m

p

To compute a

Q R

factorization without column pivoting, use F08AEF (DGEQRF).

The complex analogue of this routine is F08BSF (ZGEQPF).

9 Example

This example finds the basic solutions for the linear least squares problems

minimize {‖A x_{i} - b_{i}‖}_{2}, i = 1, 2

where

b_{1}

and

b_{2}

are the columns of the matrix

B

A = (\begin{array}{r} - 0.09 & 0.14 & - 0.46 & 0.68 & 1.29 \\ - 1.56 & 0.20 & 0.29 & 1.09 & 0.51 \\ - 1.48 & - 0.43 & 0.89 & - 0.71 & - 0.96 \\ - 1.09 & 0.84 & 0.77 & 2.11 & - 1.27 \\ 0.08 & 0.55 & - 1.13 & 0.14 & 1.74 \\ - 1.59 & - 0.72 & 1.06 & 1.24 & 0.34 \end{array}) and B = (\begin{array}{r} - 0.01 & - 0.04 \\ 0.04 & - 0.03 \\ 0.05 & 0.01 \\ - 0.03 & - 0.02 \\ 0.02 & 0.05 \\ - 0.06 & 0.07 \end{array}) .

Here

A

is approximately rank-deficient, and hence it is preferable to use F08BEF (DGEQPF) rather than F08AEF (DGEQRF).

NAG Library Routine DocumentF08BEF (DGEQPF)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

NAG Library Routine Document

F08BEF (DGEQPF)