Low rank approximation of a sparse matrix based on LU factorization with column and row tournament pivoting. (English) Zbl 1453.65090


65F55 Numerical methods for low-rank matrix approximation; matrix compression
65F50 Computational methods for sparse matrices
Full Text: DOI


[1] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. W. Demmel, J. Dongarra, J. D. Croz, A. Greenbaum, S. Hammarling, A. McKenney, and D. Sorensen, LAPACK Users’ Guide, SIAM, Philadelphia, 1999.
[2] G. Ballard, J. Demmel, O. Holtz, and O. Schwartz, Minimizing communication in numerical linear algebra, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 866–901. · Zbl 1246.68128
[3] C. H. Bischof, A parallel QR factorization algorithm with controlled local pivoting, SIAM J. Sci. and Stat. Comput., 12 (1991), pp. 36–57. · Zbl 0718.65017
[4] P. A. Businger and G. H. Golub, Linear least squares solutions by Householder transformations, Numer. Math., 7 (1965), pp. 269–276. · Zbl 0142.11503
[5] S. Chandrasekaran and I. C. F. Ipsen, On rank-revealing factorisations, SIAM. J. Matrix Anal. Appl., 15 (1994), pp. 592–622. · Zbl 0796.65030
[6] K. L. Clarkson and D. P. Woodruff, Low rank approximation and regression in input sparsity time, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing, 2013, pp. 81–90. · Zbl 1293.65069
[7] J. K. Cullum and R. A. Willoughby, Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Vol. I: Theory, SIAM, Philadelphia, 2002. · Zbl 1013.65033
[8] T. Davis, Algorithm 915, SuiteSparseQR: Multifrontal multithreaded rank-revealing sparse QR factorization, ACM Trans. Math. Software, 38 (2011), pp. 8:1–8:22. · Zbl 1365.65122
[9] T. A. Davis, J. R. Gilbert, S. I. Larimore, and E. G. Ng, A column approximate minimum degree ordering algorithm, ACM Trans. Math. Software, 30 (2004), pp. 353–376. · Zbl 1073.65039
[10] T. A. Davis and Y. Hu, The University of Florida Sparse Matrix Collection, ACM Trans. Math. Software, 38 (2011), pp. 1–25. . · Zbl 1365.65123
[11] J. Demmel, L. Grigori, M. Gu, and H. Xiang, Communication-avoiding rank-revealing QR decomposition, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 55–89. · Zbl 1327.65078
[12] J. Demmel, L. Grigori, M. Gu, and H. Xiang, LU with Tournament Pivoting for Nearly Singular Matrices, Technical report, Inria and UC Berkeley, 2018, in preparation.
[13] J. W. Demmel, L. Grigori, M. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations, SIAM J. Sci. Comput., 34 (2012), pp. 206–239. · Zbl 1241.65028
[14] J. W. Demmel, N. J. Higham, and R. Schreiber, Block LU factorization, Numer. Linear Algebra Appl., 2 (1995), pp. 173–190.
[15] L. Foster, San Jose State University Singular Matrix Database, .
[16] A. George, Nested Dissection of a Regular Finite Element Mesh, SIAM J. Numer. Anal., 10 (1973), pp. 345–363. · Zbl 0259.65087
[17] A. George and J. W.-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, Englewood Cliffs, NJ, 1981. · Zbl 0516.65010
[18] A. George, J. W.-H. Liu, and E. G.-Y. Ng, A data structure for sparse QR and LU factors, SIAM J. Sci. and Stat. Comput., 9 (1988), pp. 100–121. · Zbl 0648.65019
[19] J. R. Gilbert, E. G. Ng, and B. W. Peyton, Separators and structure prediction in sparse orthogonal factorization, Linear Algebra Appl., 262 (1997). · Zbl 0881.15015
[20] G. H. Golub, Numerical methods for solving linear least squares problems, Numer. Math., 7 (1965), pp. 206–216. · Zbl 0142.11502
[21] G. H. Golub and C. F. Van Loan, Matrix Computations, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037
[22] Z. N. Goreinov SA, Tyrtyshnikov EE, A theory of pseudoskeleton approximations, Linear Algebra Appl., 261 (1997), pp. 1–21. · Zbl 0877.65021
[23] L. Grigori, S. Cayrols, and J. Demmel, Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting, Technical report 8910, Inria, 2016. · Zbl 1453.65090
[24] L. Grigori, J. W. Demmel, and H. Xiang, CALU: A communication optimal LU factorization algorithm, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1317–1350. · Zbl 1242.65089
[25] 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
[26] 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
[27] P. C. Hansen, Regularization tools version 4.1 for MATLAB 7.3.
[28] Y. P. Hong and C.-T. Pan, Rank-revealing QR factorizations and the singular value decomposition, Math. Comp., 58 (1992), pp. 213–232. · Zbl 0743.65037
[29] G. Karypis and V. Kumar, A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes and Computing Fill-Reducing Orderings of Sparse Matrices—Version 4.0, , 1998.
[30] A. Khabou, J. W. Demmel, L. Grigori, and M. Gu, Communication avoiding LU factorization with panel rank revealing pivoting, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1401–1429. · Zbl 1279.65034
[31] R. L. Lipton and R. E. Tarjan, A separator theorem for planar graphs, SIAM J. Appl. Math., 36 (1979), pp. 177–189. · Zbl 0432.05022
[32] M. W. Mahoney, Randomized algorithms for matrices and data, Found. Trends Mach. Learn., 3 (2011), pp. 123–224. · Zbl 1232.68173
[33] L. Miranian and M. Gu, Strong rank revealing LU factorizations, Linear Algebra Appl., (2003), pp. 1–16. · Zbl 1020.65016
[34] C.-T. Pan, On the existence and computation of rank-revealing LU factorizations, Linear Algebra Appl., 316 (2000), pp. 199–222. · Zbl 0962.65023
[35] Y. Saad, Numerical Methods for Large Eigenvalue Problems, 2nd ed., SIAM, Philadelphia, 2011. · Zbl 1242.65068
[36] G. Stewart, Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix, Numer. Math., 83 (1999), pp. 313–323. · Zbl 0957.65031
[37] G. W. Stewart, The QLP approximation to the singular value decomposition, SIAM J. Sci. Comput., 20 (1999), pp. 1336–1348. · Zbl 0939.65062
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.