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