GEQP3
QR Factorization of a Rectangular Matrix

GEQP3 is a FORTRAN77 library which contains the portion of the LAPACK library that carries out the QR factorization, with column pivoting, of an M by N rectangular matrix, with N <= M.

The factorization can be written as

       A = Q *  R0 * P'

         = Q * (R) * P',
               (0)
     

• Q is an M by M orthogonal matrix;
• R0 is an M by N upper trapezoidal matrix, which is guaranteed to include a final M-N by N block of zeros.
• R is an N by N upper triangular matrix, whose diagonal elements are in descending magnitude, and some of which may be zero if the system does not have full column rank N.
• P is an N by N permutation matrix that reflects the column pivoting;

The rank of A can be estimated by the rank of R, which, in turn, can be estimated by taking a tolerance T, and comparing the consecutive diagonal elements of R to T * R(1,1). If K is the last diagonal element which is at least T * R(1,1) in magnitude, we estimate the rank as K.

Thereafter, a least squares soluation of the linear system A*X=B can be determined by:

        X = P * ( inv ( R(1:k,1:k) ) * ( Q' * B )(1:k,1:k) )
                ( 0                                        )   
      

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

GEQP3 is available in a FORTRAN77 version and a FORTRAN90 version.

Related Programs:

BAND_QR, a FORTRAN77 library which computes the QR factorization of a banded matrix, and can solve related linear systems, by Alfredo Remon, Enrique Quintana-Orti, Gregorio Quintana-Orti.

LAPACK_EXAMPLES, a FORTRAN77 program which demonstrates the use of the LAPACK linear algebra library.

LINPACK, a FORTRAN77 library which solves linear systems for a variety of matrix storage schemes, real or complex arithmetic, and single or double precision. It includes a routine for computing the singular value decomposition (SVD) of a rectangular matrix. The original version of this library is by Jack Dongarra, Jim Bunch, Cleve Moler, Pete Stewart.

QR_SOLVE, a FORTRAN77 library which computes the least squares solution of a linear system A*x=b.

References:

1. Edward Anderson, Zhaojun Bai, Christian Bischof, Susan Blackford, James Demmel, Jack Dongarra, Jeremy DuCroz, Anne Greenbaum, Sven Hammarling, Alan McKenney, Danny Sorensen,
   LAPACK User's Guide,
   Third Edition,
   SIAM, 1999,
   ISBN: 0898714478,
   LC: QA76.73.F25L36

Source Code:

• geqp3.f, the source code;
• geqp3.sh, commands to compile the source code;

Examples and Tests:

• geqp3_prb.f, a sample calling program;
• geqp3_prb.sh, commands to compile, link and run the sample calling program;
• geqp3_prb_output.txt, the output file.

List of Routines:

• DCOPY copies a vector X to a vector Y.
• DGEMM performs C = alpha*A*B + beta*C or C = alpha*A*B' + beta*C or C = alpha*A'*B + beta*C or C = alpha*A'*B' + beta*C.
• DGEMV performs y := alpha*A*x + beta*y, or y := alpha*A'*x + beta*y.
• DGEQP3 computes a QR factorization with column pivoting of a matrix A: A*P = Q*R using Level 3 BLAS.
• DGEQR2 computes a QR factorization of a real m by n matrix A: A = Q * R.
• DGEQRF computes a QR factorization of a real M-by-N matrix A: A = Q * R.
• DGER performs the rank 1 operation A := alpha*x*y' + A,
• DLAMCH determines double precision machine parameters.
• DLAMC3 forces A and B to be stored prior to doing the addition of A and B.
• DLAPY2 returns sqrt(x^2+y^2), taking care not to cause unnecessary overflow.
• DLAQP2 computes a QR factorization with column pivoting of the block A(OFFSET+1:M,1:N).
• DLAQPS computes a step of QR factorization with column pivoting of a real M-by-N matrix A by using Blas-3.
• DLARF applies a real elementary reflector H to a real m by n matrix C, from either the left or the right.
• DLARFB applies a real block reflector H or its transpose H' to a real m by n matrix C, from either the left or the right.
• DLARFG generates a real elementary reflector H of order n.
• DLARFT forms the triangular factor T of a real block reflector H of order n.
• DNRM2 returns the euclidean norm of a vector.
• DORM2R overwrites the general real m by n matrix C with Q*C, Q'*C, C*Q, or C*Q'.
• DORMQR overwrites the general real M-by-N matrix C with Q*C, C*Q, Q'*C or C*Q'.
• DSCAL scales a vector by a constant.
• DSWAP interchanges two vectors.
• DTRMM performs one of the operations B := alpha*A*B, or B=alpha*A'*B or B := alpha*B*A or B:=alpha*B*A', where A is a triangular matrix.
• DTRMV performs one of the operations x =A*x, or x=A'*x where A is a triangular matrix.
• DTRSM solves A*X = alpha*B, or A'*X=alpha*B, or X*A = alpha*B, or X*A' = alpha*B where A is a triangular matrix.
• IDAMAX finds the index of the vector element having the maximum absolute value.
• IEEECK is called from the ILAENV to verify that Infinity and possibly NaN arithmetic is safe (i.e. will not trap).
• ILADLC scans A for its last non-zero column.
• ILADLR scans A for its last non-zero row.
• ILAENV is called from the LAPACK routines to choose problem-dependent parameters for the local environment.
• IPARMQ sets problem and machine dependent parameters useful for xHSEQR and its subroutines
• LSAME returns .TRUE. if CA is the same letter as CB regardless of case.
• XERBLA is an error handler for the LAPACK routines.

You can go up one level to the FORTRAN77 source codes.