QR and LQ decompositions

QR decomposition is a best known decomposition from a whole family of orthogonal factorizations, which includes QR, LQ, RQ and QL decompositions. Here Q denotes orthogonal matrix, R and L denote upper and lower triangular matrices. ALGLIB package contains implementations of two most popular decompositions: QR and LQ. These decompositions may be used to solve full rank least squares problem, as preliminary step in the construction of the SVD decomposition, or for other tasks. QL and RQ decompositions are less popular and they are not implemented in the ALGLIB.

    1 Aglorithm
    2 Performance
    3 Subroutines
    4 Manual entries

Aglorithm

QR(LQ) decomposition is implemented in LAPACK-similar manner:

A is divided into vertical blocks, which are processed left-to-right
each block is decomposed using Level 2 algorithm
trailing blocks are updated - multiplied by Qi obtained during factorization of the current block

Performance

Unlike triangular factorization algorithms (LU, Cholesky), QR/LQ are not implemented in cache oblivious manner. Nevertheless, ALGLIB implementation of QR/LQ is still efficient enough without CPU-specific tuning. Algorithm makes use of ALGLIB BLAS, mostly of rank-k updates.

From performance point of view matrices being factorized may be divided into two classes:

square matrices or rectangular matrices where both dimensions are large. ALGLIB QR is most efficient for such problems, because algorithm spends most of its time in the Level 3 ALGLIB BLAS calls.
long narrow rectangular matrices. In such tasks algorithm spends most of its time in the Level 2 BLAS calls. Matrix profile prevents from splitting it into submatrices small enough to fit into the CPU cache. Performance is somewhat lower than in the first case.

Subroutines

ALGLIB package contains both real and complex QR(LQ) decomposition subroutines. Real subroutines are listed below:

rmatrixqr and rmatrixlq return QR/LQ decomposition in the compact form (Q and R/L rewrite A).
rmatrixqrunpackq and rmatrixlqunpackq may be used to unpack Q (full or partial unpacking).
rmatrixqrunpackr and rmatrixlqunpackl may be used to unpack triangular factors R/L.