# 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.

Parameter Names |
Description | Values | ||

Set 1 | Set 2 | Set 3 | ||

m | Matrix rows | 500 | 180 | 150 |

n | Matrix columns | 100 | 60 | 150 |

W | Workload (Mflop) | 397 | 30.5 | 45.0 |

## 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.