3Exact Factorization

In this chapter we focus on algorithms for computing a QR factorization of a tall matrix $\vec{A}\in\R^{n\times d}$, where $n\gg d$.

Classical methods¶

Classical algorithms for computing the QR factorization, such as the LAPACK methods underlying np.linalg.qr, are typically based on Householder reflections or Givens rotations. These algorithms are numerically stable and run in $O(nd^2)$ operations. However, these algorithms are inherently sequential, leading to relatively low flop-rates on modern hardware. The algorithms presented in this chapter address this shortcoming.

Other factorizations¶

Many of the ideas we discuss in this chapter can be used to compute a singular value decomposition (SVD). Alternately, on obtain an SVD decomposition of $\vec{A}$ efficiently from a QR factorization. Simply compute an SVD $\vec{R} = \vec{U}' \vec{\Sigma} \vec{V}^\T$ and then set $\vec{U} = \vec{Q} \vec{U}'$ to obtain an SVD $\vec{A} = \vec{U} \vec{\Sigma} \vec{V}^\T$.

Further Reading¶

• Epperly, 2024: Accessible blog post introducing randomized Cholesky QR

• Fan et al., 2021Balabanov, 2022Higgins et al., 2023Melnichenko et al., 2025: Recent research papers on the topic.