One of the most frequently used methods of rectangular MxN matrix orthogonal factorization is the QR decomposition. The matrix A is represented as A = QR, where Q is an orthogonal square matrix, R - upper triangular or upper trapezoid matrix (depending on the dimension of A). This decomposition is not used when solving systems of equations, because it is two times slower than LU decomposition, but sometimes it can be very useful.

Different variants of the QR decomposition (depending on the proportion of the number of rows and columns) are as follows:

During the factorization, matrix A is reduced to an upper triangular matrix by elementary reflection transformations which allow to null all the elements of a column which are located below the matrix diagonal. In that case, matrix R replaces the upper part of matrix A. The reflection transformations (matrix Q) is accumulated in the lower part of matrix A.

It should be noted that matrix Q is not stored in the lower part of matrix A. It is only information which allows to generate the matrix Q that is stored there. The matrix Q is generated as follows:

Thus, the factors which form elementary reflections replace the elements below the main diagonal of matrix A. This representation of matrix Q is effective in respect to memory usage. Nevertheless, programmers often need matrix Q and not information on how to generate it. Therefore, there are two subroutines for the QR decomposition.

The RMatrixQR subroutine performs the QR decomposition and returns the result in compact form. You can get the required number of the first columns of matrix Q by using the RMatrixQRUnpackQ procedure which allows to unpack either the whole matrix or the required number of its first rows. We can note that sometimes it is required to get only some of the first matrix columns, for instance, when performing the SVD decomposition of a matrix. The R matrix can be unpacked with the RMatrixQRUnpackR subroutine.

This algorithm is transferred from the LAPACK library.

Report a bug

C#

C# 1.0 source.
qr.csharp.zip - QR decomposition of a rectangular matrix

C++

C++ source.
qr.cpp.zip - QR decomposition of a rectangular matrix
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

C++, multiple precision arithmetic

C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
qr.mpfr.zip - QR decomposition of a rectangular matrix
mpfr.zip - precompiled Win32 MPFR/GMP binaries

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
qr.delphi.zip - QR decomposition of a rectangular matrix

Visual Basic 6

Visual Basic 6 source.
qr.vb6.zip - QR decomposition of a rectangular matrix

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
qr.zonnon.zip - QR decomposition of a rectangular matrix