Blendenpik: supercharging Lapack’s least-squares solver. 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.

References in zbMATH (referenced in 20 articles )

Showing results 1 to 20 of 20.
Sorted by year (citations)

  1. Shabat, Gil; Shmueli, Yaniv; Aizenbud, Yariv; Averbuch, Amir: Randomized LU decomposition (2018)
  2. Avron, Haim; Clarkson, Kenneth L.; Woodruff, David P.: Faster kernel ridge regression using sketching and preconditioning (2017)
  3. Clarkson, Kenneth L.; Drineas, Petros; Magdon-Ismail, Malik; Mahoney, Michael W.; Meng, Xiangrui; Woodruff, David P.: The fast Cauchy transform and faster robust linear regression (2016)
  4. Wei, Yimin; Xie, Pengpeng; Zhang, Liping: Tikhonov regularization and randomized GSVD (2016)
  5. Zhang, Xiaowei; Cheng, Li; Chu, Delin; Liao, Li-Zhi; Ng, Michael K.; Tan, Roger C.E.: Incremental regularized least squares for dimensionality reduction of large-scale data (2016)
  6. Bourgain, Jean; Dirksen, Sjoerd; Nelson, Jelani: Toward a unified theory of sparse dimensionality reduction in Euclidean space (2015)
  7. Holodnak, John T.; Ipsen, Ilse C.F.: Randomized approximation of the Gram matrix: exact computation and probabilistic bounds (2015)
  8. Ma, Ping; Mahoney, Michael W.; Yu, Bin: A statistical perspective on algorithmic leveraging (2015)
  9. Ipsen, Ilse C.F.; Wentworth, Thomas: The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems (2014)
  10. Meng, Xiangrui; Saunders, Michael A.; Mahoney, Michael W.: LSRN: A parallel iterative solver for strongly over- or underdetermined systems (2014)
  11. Needell, Deanna; Tropp, Joel A.: Paved with good intentions: analysis of a randomized block Kaczmarz method (2014)
  12. Avron, Haim; Boutsidis, Christos: Faster subset selection for matrices and applications (2013)
  13. Gratton, Serge; Jiránek, Pavel; Titley-Peloquin, David: Simple backward error bounds for linear least-squares problems (2013)
  14. Zouzias, Anastasios; Freris, Nikolaos M.: Randomized extended Kaczmarz for solving least squares (2013)
  15. Drineas, Petros; Magdon-Ismail, Malik; Mahoney, Michael W.; Woodruff, David P.: Fast approximation of matrix coherence and statistical leverage (2012)
  16. Haber, Eldad; Chung, Matthias; Herrmann, Felix: An effective method for parameter estimation with PDE constraints with multiple right-hand sides (2012)
  17. Coakley, E.S.; Rokhlin, V.; Tygert, M.: A fast randomized algorithm for orthogonal projection (2011)
  18. Drineas, Petros; Mahoney, Michael W.; Muthukrishnan, S.; Sarlós, Tamás: Faster least squares approximation (2011)
  19. Mahoney, Michael W.: Randomized algorithms for matrices and data (2011)
  20. Avron, Haim; Maymounkov, Petar; Toledo, Sivan: Blendenpik: supercharging Lapack’s least-squares solver (2010)