{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,2]],"date-time":"2026-09-02T15:27:06Z","timestamp":1788362826881,"version":"build-2803163510"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"NSF, DOE, and ONR Basic Research Challenge"},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA8750-19-2-1000"],"award-info":[{"award-number":["FA8750-19-2-1000"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006168","name":"National Nuclear Security Administration","doi-asserted-by":"publisher","award":["DENA0003525"],"award-info":[{"award-number":["DENA0003525"]}],"id":[{"id":"10.13039\/100006168","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2004235"],"award-info":[{"award-number":["2004235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2004541"],"award-info":[{"award-number":["2004541"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2004763"],"award-info":[{"award-number":["2004763"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2004850"],"award-info":[{"award-number":["2004850"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2025,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper develops and analyzes a new algorithm for QR decomposition with column pivoting (QRCP) of rectangular matrices with many more rows than columns. The algorithm carefully combines methods from randomized numerical linear algebra to accelerate pivot decisions for the input matrix and the process of decomposing the pivoted matrix into the QR form. The source of the latter improvement is CholeskyQR with randomized preconditioning. Comprehensive analysis is provided in both exact and finite-precision arithmetic to characterize the algorithm\u2019s rank-revealing properties and its numerical stability granted probabilistic assumptions of the sketching operator. An implementation of the proposed algorithm is described and made available inside the open-source RandLAPACK library, which itself relies on RandBLAS . Experiments with this implementation on an Intel Xeon Gold 6248R CPU demonstrate order-of-magnitude speedups over LAPACK \u2019s standard function for QRCP, and comparable performance to a specialized algorithm for unpivoted QR of tall matrices, which lacks the strong rank-revealing properties of the proposed method.<\/jats:p>","DOI":"10.1137\/24m163712x","type":"journal-article","created":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T03:20:05Z","timestamp":1751599205000},"page":"1701-1734","source":"Crossref","is-referenced-by-count":7,"title":["CholeskyQR with Randomization and Pivoting for Tall Matrices (CQRRPT)"],"prefix":"10.1137","volume":"46","author":[{"given":"Maksim","family":"Melnichenko","sequence":"first","affiliation":[{"name":"Corresponding author. Innovative Computing Laboratory, University of Tennessee, Knoxville, TN 37902 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4069-1448","authenticated-orcid":true,"given":"Oleg","family":"Balabanov","sequence":"additional","affiliation":[{"name":"International Computer Science Institute (ICSI), University of California, Berkeley, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1461-6458","authenticated-orcid":true,"given":"Riley","family":"Murray","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA 94550 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael W.","family":"Mahoney","sequence":"additional","affiliation":[{"name":"International Computer Science Institute (ICSI) Lawrence Berkeley National Laboratory, University of California, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0089-6965","authenticated-orcid":true,"given":"Piotr","family":"Luszczek","sequence":"additional","affiliation":[{"name":"MIT Lincoln Laboratory, Innovative Computing Laboratory, University of Tennessee, Knoxville, TN 37902 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2025,7,4]]},"reference":[{"key":"ref1","unstructured":"E. Anderson, J. Dongarra, and S. Ostrouchov, LAPACK Working Note 41 Installation Guide for LAPACK, Technical report 37996-1301, 1994."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1137\/090767911"},{"key":"ref3","unstructured":"O. Balabanov, Randomized Cholesky QR Factorizations, preprint, https:\/\/arxiv.org\/abs\/2210.09953, 2022."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1137\/120874540"},{"key":"ref5","unstructured":"O. Balabanov and L. Grigori, Randomized Block Gram-Schmidt Process for Solution of Linear Systems and Eigenvalue Problems, preprint, https:\/\/arxiv.org\/abs\/2111.14641, 2021."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/20M138870X"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436084"},{"key":"ref8","volume-title":"SIAM","author":"Bj\u00f6rk \u00c5.","year":"1996"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10444-019-09725-6"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"M. B. Cohen, Nearly tight oblivious subspace embeddings by trace inequalities, in Proceedings of the 27th annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 278\u2013287, https:\/\/doi.org\/10.1137\/1.9781611974331.ch21.","DOI":"10.1137\/1.9781611974331.ch21"},{"key":"ref11","unstructured":"J. Demmel, J. Dongarra, J. Langou, J. Langou, P. Luszczek, and M. W. Mahoney, Prospectus for the next LAPACK and ScaLAPACK libraries: Basic ALgebra LIbraries for Sustainable Technology with Interdisciplinary Collaboration (BALLISTIC), University of Tennessee, Knoxville, TN, 2020."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/22M1504901"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/15M1044680"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2842602"},{"key":"ref16","first-page":"34","volume":"68","author":"Derezinski M.","year":"2021","journal-title":"Not. AMS"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Sampling algorithms for \\(\\ell_2\\) regression and applications, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 1127\u20131136.","DOI":"10.1145\/1109557.1109682"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-010-0331-6"},{"key":"ref19","unstructured":"Y. Fan, Y. Guo, and T. Lin, A Novel Randomized XR-based Preconditioned Cholesky QR Algorithm, arXiv, 2021."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/18M1218212"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"T. Fukaya, Y. Nakatsukasa, Y. Yanagisawa, and Y. Yamamoto, Choleskyqr2: A simple and communication-avoiding algorithm for computing a tall-skinny QR factorization on a large-scale parallel system, in 2014 5th Workshop on Latest Advances in Scalable Algorithms for Large-scale Systems, 2014, pp. 31\u201338.","DOI":"10.1109\/ScalA.2014.11"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718027"},{"key":"ref25","unstructured":"N. J. Higham, What is a Rank-Revealing Factorization? 2021, (accessed 03-Apr-2023)."},{"key":"ref26","unstructured":"N. J. Higham, The Big Six Matrix Factorizations\u2014 nhigham.com, 2022, (accessed 15-Mar-2023)."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"A. J. Higgins, D. B. Szyld, E. G. Boman, and I. Yamazaki, Analysis of Randomized Householder-Cholesky QR Factorization with Multisketching, preprint, https:\/\/arxiv.org\/abs\/2309.05868, 2023.","DOI":"10.2172\/2540515"},{"key":"ref28","series-title":"Foundations and Trends in Machine Learning","volume-title":"Randomized Algorithms for Matrices and Data","author":"Mahoney M. W.","year":"2011"},{"key":"ref29","unstructured":"P.G. Martinsson, Blocked Rank-Revealing QR Factorizations: How Randomized Sampling Can be Used to Avoid Single-Vector Pivoting, preprint, https:\/\/arxiv.org\/abs\/1505.08115, 2015."},{"key":"ref30","unstructured":"R. Murray, J. Demmel, M. W. Mahoney, N. B. Erichson, M. Melnichenko, O. A. Malik, L. Grigori, P. Luszczek, M. Derezinski, M. E. Lopes, T. Liang, H. Luo, and J. Dongarra, Randomized Numerical Linear Algebra: A Perspective on the Field with an Eye to Software, preprint, https:\/\/arxiv.org\/abs\/2302.11474, 2023."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/16M1081270"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1137\/120866580"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492920000021"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"H. D. Nguyen and J. Demmel, Reproducible tall-skinny QR, in 2015 IEEE 22nd Symposium on Computer Arithmetic, 2015, pp. 152\u2013159.","DOI":"10.1109\/ARITH.2015.28"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595296732"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"T. Sarlos, Improved approximation algorithms for large matrices via random projections, in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165096"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827500370883"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2019.102571"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1177\/1094342005051521"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1142\/S1793536911000787"},{"key":"ref43","unstructured":"J. A. Tropp and R. J. Webber, Randomized Algorithms for Low-Rank Matrix Approximation: Design, Analysis, and Applications, preprint, https:\/\/arxiv.org\/abs\/2306.12418, 2023."},{"key":"ref44","doi-asserted-by":"crossref","unstructured":"J. Xiao, M. Gu, and J. Langou, Fast parallel randomized QR with column pivoting algorithms for reliable low-rank matrix approximations, in 2017 IEEE 24th International Conference on High Performance Computing (HiPC), 2017, pp. 233\u2013242.","DOI":"10.1109\/HiPC.2017.00035"},{"key":"ref45","first-page":"306","volume":"44","author":"Yamamoto Y.","year":"2015","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1137\/14M0973773"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M163712X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:53:15Z","timestamp":1787331195000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M163712X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,4]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9,30]]}},"alternative-id":["10.1137\/24M163712X"],"URL":"https:\/\/doi.org\/10.1137\/24m163712x","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,4]]}}}