EUVIMEDEUVIMED entdecken
Crossref

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

Robin Armstrong, Anil Damle

SIAM Journal on Scientific Computing · 31.08.2026 · 48 (4) · A1951-A1978

DOI: 10.1137/25m1730223 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Scientific Computing, online erschienen am 24.07.2026. Verfasst von Robin Armstrong und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 40 Literaturangaben. Gefördert von: National Science Foundation, Office of Science, Office of Naval Research SciAI Center.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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]

Förderung

  • National Science Foundation
  • Office of Science
  • Office of Naval Research SciAI Center

Zitieren

APA

Armstrong, R., & Damle, A. (2026). Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices. SIAM Journal on Scientific Computing, 48(4), A1951-A1978. https://doi.org/10.1137/25m1730223

Vancouver

Armstrong R, Damle A. Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices. SIAM Journal on Scientific Computing. 2026;48(4):A1951-A1978. doi:10.1137/25m1730223

BibTeX
@article{Armstrong2026,
  author = {Armstrong, Robin and Damle, Anil},
  title = {Collect, Commit, Expand: Efficient CPQR-Based Column Selection for Extremely Wide Matrices},
  journal = {SIAM Journal on Scientific Computing},
  year = {2026},
  volume = {48},
  number = {4},
  pages = {A1951--A1978},
  doi = {10.1137/25m1730223}
}
Kostenlos starten →