QR Factorization

The QR factorization is a linear algebra operation that factors a matrix into an orthogonal component, which is a basis for the row space of the matrix, and a triangular component. In adaptive signal processing, the QR is often used in conjunction with a triangular solver.

The QR factorization of an m × n matrix A with m ≥ n is a pair of matrices A = QR, where the unitary matrix Q is of size m × m and the upper-triangular matrix R is of size m × n. There are many ways of calculating the QR factorization, as discussed in Golub and Van Loan, including the Householder transformation method [1, Algorithm 5.2.1], the Modified Gram-Schmidt algorithm [1, Algorithm 5.2.5], and the Fast Givens method [1, Algorithm 5.2.4]. Of these, we chose to specify the Fast Givens method for this kernel benchmark. This was primarily done because the Fast Givens method consists of a number of fine grain calculations. This structure is very suitable for implementation as a stream algorithm on architectures such as the MIT RAW machine. For more details, see Hoffmann [2]. The data matrix sizes that we define for this kernel, and the corresponding workloads for calculating the QR factorization, are given in Table 1.

References

1. Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, 3rd edition, 1996.
2. Henry Hoffmann. Stream Algorithms and Architecture. Master’s thesis, Massachusetts Institute of Technology, Cambridge, MA, 2003.