3 Exact 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 other factorizations. For instance to compute a singular value decomposition (SVD), 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$.

This may be relevant for computing the matrix-sign function, which is used in the Muon optimizer Jordan et al., 2024 for training LLMs; see also Appendix F in Amsel et al., 2025.

Further Reading¶

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

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