Householder QR factorization with randomization for column pivoting (HQRRP). (English) Zbl 1365.65070


65F05 Direct numerical methods for linear systems and matrix inversion
Full Text: DOI arXiv


[1] B. K. Alpert, Hybrid Gauss-trapezoidal quadrature rules, SIAM J. Sci. Comput., 20 (1999), pp. 1551–1584. · Zbl 0933.41019
[3] E. Anderson, Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. J. Dongarra, J. D. Croz, S. Hammarling, A. Greenbaum, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, 3rd ed., SIAM, Philadelphia, 1999. · Zbl 0934.65030
[4] C. Bischof and C. Van Loan, The WY representation for products of Householder matrices, SIAM J. Sci. Statist. Comput., 8 (1987), pp. s2–s13. · Zbl 0628.65033
[5] C. H. Bischof and G. Quintana-Ortí, Algorithm 782: Codes for rank-revealing QR factorizations of dense matrices, ACM Trans. Math. Software, 24 (1998), pp. 254–257. · Zbl 0932.65034
[6] C. H. Bischof and G. Quintana-Ortí, Computing rank-revealing QR factorizations of dense matrices, ACM Trans. Math. Software, 24 (1998), pp. 226–253. · Zbl 0932.65033
[7] J. J. Dongarra, J. Du Croz, S. Hammarling, and I. Duff, A set of level 3 basic linear algebra subprograms, ACM Trans. Math. Software, 16 (1990), pp. 1–17. · Zbl 0900.65115
[8] J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst, Solving Linear Systems on Vector and Shared Memory Computers, SIAM, Philadelphia, 1991.
[9] P. Drineas, R. Kannan, and M. W. Mahoney, Fast Monte Carlo algorithms for matrices. II. Computing a low-rank approximation to a matrix, SIAM J. Comput., 36 (2006), pp. 158–183. · Zbl 1111.68148
[10] J. Duersch and M. Gu, True BLAS-3 Performance QRCP Using Random Sampling, preprint, , 2015.
[11] C. Eckart and G. Young, The approximation of one matrix by another of lower rank, Psychometrika, 1 (1936), pp. 211–218. · JFM 62.1075.02
[12] A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low-rank approximations, J. ACM, 51 (2004), pp. 1025–1041. · Zbl 1125.65005
[13] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996. · Zbl 0865.65009
[14] K. Goto and R. A. Geijn, Anatomy of high-performance matrix multiplication, ACM Trans. Math. Software, 34 (2008), p. 12. · Zbl 1190.65064
[15] K. Goto and R. A. van de Geijn, On Reducing TLB Misses in Matrix Multiplication, Tech. Report CS-TR-02-55, Department of Computer Sciences, The University of Texas at Austin, 2002.
[16] M. Gu and S. C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM J. Sci. Comput., 17 (1996), pp. 848–869. · Zbl 0858.65044
[17] J. A. Gunnels, F. G. Gustavson, G. M. Henry, and R. A. van de Geijn, FLAME: Formal Linear Algebra Methods Environment, ACM Trans. Math. Software, 27 (2001), pp. 422–455, . · Zbl 1070.65522
[18] N. Halko, P.-G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., 53 (2011), pp. 217–288. · Zbl 1269.65043
[21] T. Joffrain, T. M. Low, E. S. Quintana-Ortí, R. van de Geijn, and F. G. Van Zee, Accumulating Householder transformations, revisited, ACM Trans. Math. Software, 32 (2006), pp. 169–179, . · Zbl 1365.65106
[22] W. Kahan, Numerical linear algebra, Canad. Math. Bull, 9 (1966), pp. 757–801. · Zbl 0236.65025
[23] E. Liberty, F. Woolfe, P.-G. Martinsson, V. Rokhlin, and M. Tygert, Randomized algorithms for the low-rank approximation of matrices, Proc. Natl. Acad. Sci. USA, 104 (2007), pp. 20167–20172, . · Zbl 1215.65080
[24] M. W. Mahoney, Randomized algorithms for matrices and data, Found. Trends Machine Learning, 3 (2011), pp. 123–224. · Zbl 1232.68173
[25] P. Martinsson, Blocked Rank-Revealing Gr Factorizations: How Randomized Sampling Can Be Used to Avoid Single-Vector Pivoting, preprint, , 2015.
[26] P.-G. Martinsson, V. Rokhlin, and M. Tygert, A Randomized Algorithm for the Approximation of Matrices, Yale CS research report YALEU/DCS/RR-1361, Computer Science Department, Yale University, 2006. · Zbl 1210.65095
[27] P.-G. Martinsson, V. Rokhlin, and M. Tygert, A randomized algorithm for the decomposition of matrices, Appl. Comput. Harmon. Anal., 30 (2011), pp. 47–68, . · Zbl 1210.65095
[28] P.-G. Martinsson and S. Voronin, A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices, SIAM J. Sci. Comput., 38 (2016), pp. S485–S507. · Zbl 1352.65095
[29] J. Poulson, B. Marker, R. A. van de Geijn, J. R. Hammond, and N. A. Romero, Elemental: A new framework for distributed memory dense matrix computations, ACM Trans. Math. Softw., 39 (2013), p. 13. · Zbl 1295.65137
[30] E. S. Quintana, G. Quintana, X. Sun, and R. van de Geijn, A note on parallel matrix inversion, SIAM J. Sci. Comput., 22 (2001), pp. 1762–1771. · Zbl 0991.65029
[31] G. Quintana-Ortí, X. Sun, and C. H. Bischof, A BLAS-3 version of the QR factorization with column pivoting, SIAM J. Sci. Comput., 19 (1998), pp. 1486–1494, . · Zbl 0912.65034
[32] R. Schreiber and C. Van Loan, A storage-efficient WY representation for products of Householder transformations, SIAM J. Sci. Statist. Comput., 10 (1989), pp. 53–57. · Zbl 0664.65025
[33] G. Stewart, Matrix Algorithms Volume 1: Basic Decompositions, SIAM, Philadelphia, 1998. · Zbl 0910.65012
[34] F. G. Van Zee, libflame: The Complete Reference, , (2012).
[35] F. G. Van Zee, E. Chan, R. van de Geijn, E. S. Quintana-Ortí, and G. Quintana-Ortí, The libflame library for dense matrix computations, IEEE Comput. Sci. Eng., 11 (2009), pp. 56–62.
[36] F. G. Van Zee and R. A. van de Geijn, BLIS: A framework for rapidly instantiating BLAS functionality, ACM Trans. Math. Software, 41 (2015). · Zbl 1347.65054
[37] S. Voronin and P. Martinsson, A CUR Factorization Algorithm Based on the Interpolative Decomposition, , 2014.
[38] D. P. Woodruff, Sketching as a Tool for Numerical Linear Algebra, preprint, , 2014. · Zbl 1316.65046
[39] X. Zhang, Q. Wang, and Y. Zhang, Model-driven level 3 BLAS performance optimization on Loongson 3a processor, in Proceedings of the 18th International Conference on Parallel and Distributed Systems, IEEE Computer Society, 2012, pp. 684–691.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.