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

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

1 2 next

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

1 2 next