{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T21:41:54Z","timestamp":1780609314097,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:00:00Z","timestamp":1649116800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T00:00:00Z","timestamp":1649116800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"publisher","award":["BIRD192932"],"award-info":[{"award-number":["BIRD192932"]}],"id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we introduce a new column selection strategy, named here \u201cDeviation Maximization\u201d, and apply it to compute rank-revealing QR factorizations as an alternative to the well-known block version of the QR factorization with the column pivoting method, called QP3 and currently implemented in LAPACK\u2019s  routine. We show that the resulting algorithm, named QRDM, has similar rank-revealing properties of QP3 and better execution times. We present experimental results on a wide data set of numerically singular matrices, which has become a reference in the recent literature.<\/jats:p>","DOI":"10.1007\/s11075-022-01291-1","type":"journal-article","created":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T14:33:49Z","timestamp":1649169229000},"page":"1047-1079","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Deviation maximization for rank-revealing QR factorizations"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2727-9123","authenticated-orcid":false,"given":"Monica","family":"Dessole","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabio","family":"Marcuzzi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,4,5]]},"reference":[{"key":"1291_CR1","doi-asserted-by":"crossref","unstructured":"Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users\u2019 Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA, 3rd edn. ISBN 0-89871-447-8 (paperback) (1999)","DOI":"10.1137\/1.9780898719604"},{"key":"1291_CR2","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1137\/0727045","volume":"27","author":"J Barlow","year":"1990","unstructured":"Barlow, J., Demmel, J.: Computing accurate eigensystems of scaled diagonally dominant matrices. SIAM J. Numer. Anal. 27, 11 (1990). https:\/\/doi.org\/10.1137\/0727045","journal-title":"SIAM J. Numer. Anal."},{"key":"1291_CR3","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/BF02139475","volume":"2","author":"C Bischof","year":"1992","unstructured":"Bischof, C., Hansen, P.: A block algorithm for computing rank-revealing QR factorizations. Numer. Algo. 2, 371\u2013391,10 (1992). https:\/\/doi.org\/10.1007\/BF02139475","journal-title":"Numer. Algo."},{"key":"1291_CR4","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1145\/290200.287637","volume":"24","author":"C Bischof","year":"1998","unstructured":"Bischof, C., Quintana-Ort\u00ed, G.: Computing rank-revealing QR factorizations of dense matrices. ACM Trans. Math. Softw. 24, 226\u2013253, 06 (1998a). https:\/\/doi.org\/10.1145\/290200.287637","journal-title":"ACM Trans. Math. Softw."},{"key":"1291_CR5","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1145\/290200.287638","volume":"24","author":"C Bischof","year":"1998","unstructured":"Bischof, C., Quintana-Ort\u00ed, G.: Algorithm 782: codes for Rank-Revealing QR factorizations of dense matrices. ACM Trans. Math. Softw. 24, 254\u2013257, 07 (1998b). https:\/\/doi.org\/10.1145\/290200.287638","journal-title":"ACM Trans. Math. Softw."},{"key":"1291_CR6","doi-asserted-by":"publisher","unstructured":"Bischof, J.R.: A block QR factorization algorithm using restricted pivoting. In: Supercomputing \u201989:Proceedings of the 1989 ACM\/IEEE Conference on Supercomputing, pp. 248\u2013256. https:\/\/doi.org\/10.1145\/76263.76290 (1989)","DOI":"10.1145\/76263.76290"},{"issue":"3","key":"1291_CR7","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01436084","volume":"7","author":"P Businger","year":"1965","unstructured":"Businger, P., Golub, G.H.: Linear Least Squares Solutions by Householder Transformations. Numer. Math. 7(3), 269\u2013276 (1965). ISSN 0029-599X. https:\/\/doi.org\/10.1007\/BF01436084","journal-title":"Numer. Math."},{"key":"1291_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0024-3795(87)90103-0","volume":"88-89","author":"TF Chan","year":"1987","unstructured":"Chan, T.F.: Rank revealing QR factorizations. Linear Algebra Appl. 88-89, 67\u201382 (1987). ISSN 0024-3795. https:\/\/doi.org\/10.1016\/0024-3795(87)90103-0. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379587901030","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1291_CR9","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1137\/S0895479891223781","volume":"15","author":"S Chandrasekaran","year":"1994","unstructured":"Chandrasekaran, S., Ipsen, I.C.F.: On Rank-Revealing factorisations. SIAM J. Matrix Anal. Appl. 15(2), 592\u2013622 (1994). https:\/\/doi.org\/10.1137\/S0895479891223781","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1291_CR10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1137\/13092157X","volume":"36","author":"J Demmel","year":"2015","unstructured":"Demmel, J., Grigori, L., Gu, M., Xiang, H.: Communication avoiding rank revealing QR factorization with column pivoting. SIAM J. Matrix Anal. Appl. 36, 55\u201389, 01 (2015). https:\/\/doi.org\/10.1137\/13092157X","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1291_CR11","doi-asserted-by":"publisher","first-page":"20","DOI":"10.14658\/PUPJ-DRNA-2020-1-3","volume":"13","author":"M Dessole","year":"2020","unstructured":"Dessole, M., Marcuzzi, F., Vianello, M.: Accelerating the Lawson-Hanson NNLS solver for large-scale Tchakaloff regression designs. Dolomites Research Notes on Approximation 13, 20\u201329 (2020a). ISSN 2035-6803. https:\/\/doi.org\/10.14658\/PUPJ-DRNA-2020-1-3. https:\/\/drna.padovauniversitypress.it\/2020\/1\/3","journal-title":"Dolomites Research Notes on Approximation"},{"key":"1291_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.3390\/math8071122","volume":"8","author":"M Dessole","year":"2020","unstructured":"Dessole, M., Marcuzzi, F., Vianello, M.: DCATCH\u2014a numerical package for d-variate near g-optimal Tchakaloff regression via fast NNLS. Mathematics 8, 7 (2020b). https:\/\/doi.org\/10.3390\/math8071122","journal-title":"Mathematics"},{"key":"1291_CR13","doi-asserted-by":"publisher","unstructured":"Drma\u010d, Z., Bujanovi\u0107, Z.: On the Failure of Rank-Revealing QR Factorization Software \u2013 A Case Study. ACM Trans. Math. Softw. 35(2). ISSN 0098-3500. https:\/\/doi.org\/10.1145\/1377612.1377616 (2008)","DOI":"10.1145\/1377612.1377616"},{"issue":"4","key":"1291_CR14","doi-asserted-by":"publisher","first-page":"C263","DOI":"10.1137\/15M1044680","volume":"39","author":"JA Duersch","year":"2017","unstructured":"Duersch, J.A., Gu, M.: Randomized QR with column pivoting. SIAM J. Sci. Comput. 39(4), C263\u2013C291 (2017). https:\/\/doi.org\/10.1137\/15M1044680","journal-title":"SIAM J. Sci. Comput."},{"key":"1291_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0024-3795(86)90115-1","volume":"74","author":"LV Foster","year":"1986","unstructured":"Foster, L.V.: Rank and null space calculations using matrix decomposition without column interchanges. Linear Algebra Appl. 74, 47\u201371 (1986). ISSN 0024-3795. https:\/\/doi.org\/10.1016\/0024-3795(86)90115-1. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379586901151","journal-title":"Linear Algebra Appl."},{"issue":"3","key":"1291_CR16","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/BF01436075","volume":"7","author":"G Golub","year":"1965","unstructured":"Golub, G.: Numerical methods for solving linear least squares problems. Numer. Math. 7(3), 206\u2013216 (1965). ISSN 0029-599X. https:\/\/doi.org\/10.1007\/BF01436075","journal-title":"Numer. Math."},{"key":"1291_CR17","volume-title":"Matrix Computations (4th ed.). Johns Hopkins Studies in the Mathematical Sciences","author":"G Golub","year":"2013","unstructured":"Golub, G., Van Loan, C.: Matrix Computations (4th ed.). Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2013). ISBN 9781421407944"},{"key":"1291_CR18","volume-title":"Rank degeneracy and least squares problems. Technical Report STAN-CS-76-559","author":"G Golub","year":"1976","unstructured":"Golub, G., Klema, V., Stewart, G.W.: Rank degeneracy and least squares problems. Technical Report STAN-CS-76-559. Department of Computer Science Stanford University, Stanford (1976)"},{"issue":"4","key":"1291_CR19","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1137\/0917055","volume":"17","author":"M Gu","year":"1996","unstructured":"Gu, M., Eisenstat, S. C.: Efficient algorithms for computing a strong Rank-Revealing QR factorization. SIAM J. Sci. Comput. 17(4), 848\u2013869 (1996). https:\/\/doi.org\/10.1137\/0917055","journal-title":"SIAM J. Sci. Comput."},{"key":"1291_CR20","volume-title":"Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion","author":"PC Hansen","year":"1999","unstructured":"Hansen, P.C.: Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. Society for Industrial and Applied Mathematics, USA (1999). ISBN 0898714036"},{"issue":"4","key":"1291_CR21","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1137\/1029112","volume":"29","author":"NJ Higham","year":"1987","unstructured":"Higham, N.J.: A survey of condition number estimation for triangular matrices. SIAM Rev. 29(4), 575\u2013596 (1987). ISSN 0036-1445. https:\/\/doi.org\/10.1137\/1029112","journal-title":"SIAM Rev."},{"issue":"197","key":"1291_CR22","first-page":"213","volume":"58","author":"YP Hong","year":"1992","unstructured":"Hong, Y.P., Pan, C.-T.: Rank-revealing QR factorizations and the singular value decomposition. Math. Comput. 58(197), 213\u2013232 (1992). ISSN 00255718, 10886842. http:\/\/www.jstor.org\/stable\/2153029","journal-title":"Math. Comput."},{"key":"1291_CR23","doi-asserted-by":"publisher","first-page":"757","DOI":"10.4153\/CMB-1966-083-2","volume":"9","author":"W Kahan","year":"1966","unstructured":"Kahan, W.: Numerical linear algebra. Can. Math. Bull. 9, 757\u2013801 (1966)","journal-title":"Can. Math. Bull."},{"key":"1291_CR24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971217","volume-title":"Solving least squares problems, vol. 15","author":"CL Lawson","year":"1995","unstructured":"Lawson, C. L., Hanson, R.J.: Solving least squares problems, vol. 15. SIAM, Bangkok (1995)"},{"key":"1291_CR25","unstructured":"Martinsson, P.G.: Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting. Report, 05. arXiv:1505.08115 (2015)"},{"key":"1291_CR26","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.laa.2017.10.014","volume":"538","author":"A Mikhalev","year":"2018","unstructured":"Mikhalev, A., Oseledets, I.: Rectangular maximum-volume submatrices and their applications. Linear Algebra Appl. 538, 187\u2013211 (2018). ISSN 0024-3795. https:\/\/doi.org\/10.1016\/j.laa.2017.10.014. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0024379517305931","journal-title":"Linear Algebra Appl."},{"issue":"5","key":"1291_CR27","doi-asserted-by":"publisher","first-page":"1486","DOI":"10.1137\/S1064827595296732","volume":"19","author":"G Quintana-Ort\u00ed","year":"1998","unstructured":"Quintana-Ort\u00ed, G., Sun, X., Bischof, C. H.: A BLAS-3 version of the QR factorization with column pivoting. SIAM J. Sci. Comput. 19(5), 1486\u20131494 (1998). https:\/\/doi.org\/10.1137\/S1064827595296732","journal-title":"SIAM J. Sci. Comput."},{"key":"1291_CR28","doi-asserted-by":"publisher","first-page":"02","DOI":"10.1137\/0910005","volume":"10","author":"R Schreiber","year":"1989","unstructured":"Schreiber, R., VanLoan, C.: A Storage-Efficient WY representation for products of householder transformations. SIAM J. Sci. Stat. Comput. 10, 02 (1989). https:\/\/doi.org\/10.1137\/0910005","journal-title":"SIAM J. Sci. Stat. Comput."},{"issue":"1","key":"1291_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0024-3795(72)90013-4","volume":"5","author":"R Thompson","year":"1972","unstructured":"Thompson, R.: Principal submatrices IX: Interlacing inequalities for singular values of submatrices. Linear Algebra Appl. 5(1), 1\u201312 (1972). ISSN 0024-3795. https:\/\/doi.org\/10.1016\/0024-3795(72)90013-4. https:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379572900134","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1291_CR30","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0024-3795(75)90112-3","volume":"11","author":"J Varah","year":"1975","unstructured":"Varah, J.: A lower bound for the smallest singular value of a matrix. Linear Algebra Appl. 11(1), 3\u20135 (1975). ISSN 0024-3795. https:\/\/doi.org\/10.1016\/0024-3795(75)90112-3. http:\/\/www.sciencedirect.com\/science\/article\/pii\/0024379575901123","journal-title":"Linear Algebra Appl."},{"key":"1291_CR31","doi-asserted-by":"publisher","unstructured":"Xiao, J., Gu, M., Langou, J.: 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), pp. 233\u2013242, 12. https:\/\/doi.org\/10.1109\/HiPC.2017.00035 (2017)","DOI":"10.1109\/HiPC.2017.00035"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-022-01291-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-022-01291-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-022-01291-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T07:22:56Z","timestamp":1665040976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-022-01291-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,5]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1291"],"URL":"https:\/\/doi.org\/10.1007\/s11075-022-01291-1","relation":{},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,5]]},"assertion":[{"value":"4 June 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"<!--Emphasis Type='Bold' removed-->Conflict of interest"}}]}}