Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting

Understand

Given a matrix $A$ of size $m\times n$, the manuscript describes a algorithm for computing a QR factorization $AP=QR$ where $P$ is a permutation matrix, $Q$ is orthonormal, and $R$ is upper triangular.

• The algorithm is blocked, to allow it to be implemented efficiently.
• The need for single vector pivoting in classical algorithms for computing QR factorizations is avoided by the use of randomized sampling to find blocks of pivot vectors at once.
• The advantage of blocking becomes particularly pronounced when $A$ is very large, and possibly stored out-of-core, or on a distributed memory machine.