{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,27]],"date-time":"2026-09-27T01:41:16Z","timestamp":1790473276741,"version":"4.1.0"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>In this paper we introduce CARRQR, a communication avoiding rank revealing QR factorization with tournament pivoting. We show that CARRQR reveals the numerical rank of a matrix in an analogous way to QR factorization with column pivoting (QRCP). Although the upper bound of a quantity involved in the characterization of a rank revealing factorization is worse for CARRQR than for QRCP, our numerical experiments on a set of challenging matrices show that this upper bound is very pessimistic, and CARRQR is an effective tool in revealing the rank in practical problems. Our main motivation for introducing CARRQR is that it minimizes data transfer, modulo polylogarithmic factors, on both sequential and parallel machines, while previous factorizations as QRCP are communication suboptimal and require asymptotically more communication than CARRQR. Hence CARRQR is expected to have a better performance on current and future computers, where communication is a major bottleneck that highly impacts the performance of an algorithm.<\/jats:p>","DOI":"10.1137\/13092157x","type":"journal-article","created":{"date-parts":[[2015,1,22]],"date-time":"2015-01-22T12:37:06Z","timestamp":1421930226000},"page":"55-89","source":"Crossref","is-referenced-by-count":64,"title":["Communication Avoiding Rank Revealing QR Factorization with Column Pivoting"],"prefix":"10.1137","volume":"36","author":[{"given":"James W.","family":"Demmel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laura","family":"Grigori","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Gu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hua","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen,\n                      LAPACK Users' Guide\n                      , SIAM, Philadelphia, 1999.","DOI":"10.1137\/1.9780898719604"},{"key":"atypb2","unstructured":"G. Ballard, J. Demmel, and I. Dumitriu,\n                      Minimizing Communication for Eigenproblems and the Singular Value Decomposition\n                      , Tech. Report UCB\/EECS-2011-14, EECS Department, University of California, Berkeley, 2011."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/090769156"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/0912002"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"L. S. Blackford, J. Choi, A. Cleary, E. D'Azevedo, J. Demmel, I. Dhillon, J. Dongarra, S. Hammarling, G. Henry, A. Petitet, K. Stanley, D. Walker, and R. C. Whaley,\n                      ScaLAPACK Users' Guide\n                      , SIAM, Philadelphia, 1997.","DOI":"10.1137\/1.9780898719642"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436084"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90103-0"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0913043"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479891223781"},{"key":"atypb10","doi-asserted-by":"crossref","unstructured":"J. W. Demmel, L. Grigori, M. Gu, and H. Xiang,\n                      Communication Avoiding Rank Revealing QR Factorization with Column Pivoting\n                      , Tech. Report EECS-2013-46, INRIA, Paris, and University of California, Berkeley, 2013.","DOI":"10.21236\/ADA584728"},{"key":"atypb11","unstructured":"J. Demmel, L. Grigori, M. F. Hoemmen, and J. Langou,\n                      Communication-Avoiding Parallel and Sequential QR and LU Factorizations: Theory and Practice\n                      , Tech. Report UCB\/EECS-2008-89, EECS Department, University of California, Berkeley, 2008."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/080731992"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1145\/1377612.1377616"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/050639193"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1137\/05063920X"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436075"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"G. H. Golub, V. Klema, and G. W. Stewart,\n                      Rank Degeneracy and Least Squares Problems\n                      , Tech. Report TR-456, Department of Computer Science, University of Maryland, College Park, MD, 1976.","DOI":"10.3386\/w0165"},{"key":"atypb20","first-page":"29","author":"Grigori L.","year":"2008","journal-title":"NJ"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/100788926"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0917055"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , 2nd ed., SIAM, Philadelphia, 2002.","DOI":"10.1137\/1.9780898718027"},{"key":"atypb25","first-page":"213","volume":"58","author":"Hong Y. P.","year":"1992","journal-title":"Math. Comp."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1002\/nla.404"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/120863691"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827595296732"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827597319519"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/13092157X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:42:21Z","timestamp":1787326941000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/13092157X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/13092157X"],"URL":"https:\/\/doi.org\/10.1137\/13092157x","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}