{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,17]],"date-time":"2026-11-17T04:40:53Z","timestamp":1794890453410,"version":"4.9.1"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Several innovative random-sampling and random-mixing techniques for solving problems in linear algebra have been proposed in the last decade, but they have not yet made a significant impact on numerical linear algebra. We show that by using a high-quality implementation of one of these techniques, we obtain a solver that performs extremely well in the traditional yardsticks of numerical linear algebra: it is significantly faster than high-performance implementations of existing state-of-the-art algorithms, and it is numerically backward stable. More specifically, we describe a least-squares solver for dense highly overdetermined systems that achieves residuals similar to those of direct QR factorization-based solvers (lapack), outperforms lapack by large factors, and scales significantly better than any QR-based solver.<\/jats:p>","DOI":"10.1137\/090767911","type":"journal-article","created":{"date-parts":[[2010,4,23]],"date-time":"2010-04-23T18:21:47Z","timestamp":1272046907000},"page":"1217-1236","source":"Crossref","is-referenced-by-count":143,"title":["Blendenpik: Supercharging LAPACK's Least-Squares Solver"],"prefix":"10.1137","volume":"32","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Petar","family":"Maymounkov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,4,23]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"N. Ailon and B. Chazelle,\n                      Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform\n                      , in Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York, 2006, pp. 557\u2013563.","DOI":"10.1145\/1132516.1132597"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"N. Ailon and E. Liberty,\n                      Fast dimension reduction using Rademacher series on dual BCH codes\n                      , in Proceedings of the 19th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2008, pp. 1\u20139.","DOI":"10.21236\/ADA471857"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/070698725"},{"key":"R4","unstructured":"H. Avron,\n                      Efficient and Robust Hybrid Iterative-Direct Multipurpose Linear Solvers\n                      , Ph.D. thesis, Tel-Aviv University, Israel, expected October 2010."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2009.03.026"},{"key":"R6","unstructured":"E. J. Cand\u00e8s and B. Recht,\n                      Exact matrix completion via convex optimization\n                      , Tecnical report CoRR, abs\/0805.4471 (2008)."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/080724071"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/070696507"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-007-0114-x"},{"key":"R10","unstructured":"P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarl\u00f3s,\n                      Faster least squares approximation\n                      , Tecnical report, CoRR, abs\/0710.1435 (2007)."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"P. Drineas, M. W. Mahoney, and S. Muthukrishnan,\n                      Sampling algorithms for $l2$ regression and applications\n                      , in Proceedings of the 17th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, ACM, New York, 2006, pp. 1127\u20131136.","DOI":"10.1145\/1109557.1109682"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/07070471X"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"J. Johnson and M. Puschel,\n                      In search of the optimal Walsh-Hadamard transform\n                      , in Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing, Washington, DC, 2000, pp. 3347\u20133350.","DOI":"10.1109\/ICASSP.2000.860117"},{"key":"R14","unstructured":"M. Kac,\n                      Probability and Related Topics in Physical Science\n                      , Wiley Interscience, New York, 1959."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0803205106"},{"key":"R16","unstructured":"MATLAB, version 7.7, software package, The MathWorks, 2008."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"N. H. Nguyen, T. T. Do, and T. D. Tran,\n                      A fast and efficient algorithm for low-rank approximation of a matrix\n                      , in Proceedings of the 41st ACM Symposium on Theory of Computing, New York, 2009, pp. 215\u2013224.","DOI":"10.1145\/1536414.1536446"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"R19","unstructured":"C. C. Paige,\n                      The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices\n                      , Ph.D. thesis, University of London, 1971."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1979-0514820-3"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/080736417"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0804869105"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"T. Sarlos,\n                      Improved approximation algorithms for large matrices via random projections\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, 2006, pp. 143\u2013152.","DOI":"10.1109\/FOCS.2006.37"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/78.205723"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"G. W. Stewart,\n                      Matrix Algorithms Volume\n                      II:\n                      Eigensystems\n                      , SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718058"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"R. C. Whaley and A. Petitet,\n                      Minimizing development and maintenance costs in supporting persistently optimized BLAS\n                      , Software: Practice and Experience, 35 (2005), pp. 101\u2013121, also online at http:\/\/www.cs.utsa.edu\/~whaley\/papers\/spercw04.ps.","DOI":"10.1002\/spe.626"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/090767911","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T16:12:21Z","timestamp":1787328741000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/090767911"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/090767911"],"URL":"https:\/\/doi.org\/10.1137\/090767911","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}