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 16 articles )

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

  1. 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)
  2. Wei, Yimin; Xie, Pengpeng; Zhang, Liping: Tikhonov regularization and randomized GSVD (2016)
  3. 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)
  4. Bourgain, Jean; Dirksen, Sjoerd; Nelson, Jelani: Toward a unified theory of sparse dimensionality reduction in Euclidean space (2015)
  5. Ma, Ping; Mahoney, Michael W.; Yu, Bin: A statistical perspective on algorithmic leveraging (2015)
  6. Meng, Xiangrui; Saunders, Michael A.; Mahoney, Michael W.: LSRN: A parallel iterative solver for strongly over- or underdetermined systems (2014)
  7. Needell, Deanna; Tropp, Joel A.: Paved with good intentions: analysis of a randomized block Kaczmarz method (2014)
  8. Avron, Haim; Boutsidis, Christos: Faster subset selection for matrices and applications (2013)
  9. Gratton, Serge; Jiránek, Pavel; Titley-Peloquin, David: Simple backward error bounds for linear least-squares problems (2013)
  10. Zouzias, Anastasios; Freris, Nikolaos M.: Randomized extended Kaczmarz for solving least squares (2013)
  11. Drineas, Petros; Magdon-Ismail, Malik; Mahoney, Michael W.; Woodruff, David P.: Fast approximation of matrix coherence and statistical leverage (2012)
  12. Haber, Eldad; Chung, Matthias; Herrmann, Felix: An effective method for parameter estimation with PDE constraints with multiple right-hand sides (2012)
  13. Coakley, E.S.; Rokhlin, V.; Tygert, M.: A fast randomized algorithm for orthogonal projection (2011)
  14. Drineas, Petros; Mahoney, Michael W.; Muthukrishnan, S.; Sarlós, Tamás: Faster least squares approximation (2011)
  15. Mahoney, Michael W.: Randomized algorithms for matrices and data (2011)
  16. Avron, Haim; Maymounkov, Petar; Toledo, Sivan: Blendenpik: supercharging Lapack’s least-squares solver (2010)