Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices

Abstract. Column-pivoted QR (CPQR) factorization is a computational primitive used in numerous applications that require selecting a small set of “representative” columns from a much larger matrix. These include applications in spectral clustering, model-order reduction, low-rank approximation, and computational quantum chemistry, where the matrix being factorized has a moderate number of rows but an extremely large number of columns. We describe a modification of the Golub–Businger algorithm which, for many matrices of this type, can perform CPQR-based column selection much more efficiently. This algorithm, which we call CCEQR, is based on a three-step “collect, commit, expand” strategy that limits the number of columns being manipulated, while also transferring more computational effort from level-2 BLAS to level-3. Unlike most CPQR algorithms that exploit level-3 BLAS, CCEQR is deterministic and provably recovers a column permutation equivalent to the one computed by the Golub–Businger algorithm. Tests on spectral clustering and Wannier basis localization problems demonstrate that on appropriately structured problems, CCEQR can significantly outperform GEQP3. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and Data Available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/robin-armstrong/cceqr-experiments and in the supplementary materials ( cceqr-experiments-main.zip [36.1KB], CCEQR_jl-main.zip [6.76KB]), linked from the main article webpage. [Formula: see text]