Grigori, Laura; Cayrols, Sebastien; Demmel, James W. Low rank approximation of a sparse matrix based on LU factorization with column and row tournament pivoting. (English) Zbl 1453.65090 SIAM J. Sci. Comput. 40, No. 2, C181-C209 (2018). Summary: In this paper we present an algorithm for computing a low rank approximation of a sparse matrix based on a truncated LU factorization with column and row permutations. We present various approaches for determining the column and row permutations that show a trade-off between speed versus deterministic/probabilistic accuracy. We show that if the permutations are chosen by using tournament pivoting based on QR factorization, then the obtained truncated LU factorization with column/row tournament pivoting, LU_CRTP, satisfies bounds on the singular values which have similarities with the ones obtained by a communication avoiding rank revealing QR factorization. Experiments on challenging matrices show that LU_CRTP provides a good low rank approximation of the input matrix and it is less expensive than the rank revealing QR factorization in terms of computational and memory usage costs, while also minimizing the communication cost. We also compare the computational complexity of our algorithm with randomized algorithms and show that for sparse matrices and high enough but still modest accuracies, our approach is faster. Cited in 8 Documents MSC: 65F55 Numerical methods for low-rank matrix approximation; matrix compression 65F50 Computational methods for sparse matrices Keywords:rank revealing; LU and QR factorizations; column pivoting; minimize communication Software:COLAMD; symrcm; SparseMatrix; LAPACK; SuiteSparseQR; CALU; Regularization tools; SuitSparseQR PDFBibTeX XMLCite \textit{L. Grigori} et al., SIAM J. Sci. Comput. 40, No. 2, C181--C209 (2018; Zbl 1453.65090) Full Text: DOI References: [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, {\it LAPACK Users’ Guide}, SIAM, Philadelphia, 1999. [2] G. Ballard, J. Demmel, O. Holtz, and O. Schwartz, {\it Minimizing communication in numerical linear algebra}, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 866-901. · Zbl 1246.68128 [3] C. H. Bischof, {\it 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, {\it 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, {\it 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, {\it 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, {\it Lanczos Algorithms for Large Symmetric Eigenvalue Computations, Vol. I: Theory}, SIAM, Philadelphia, 2002. · Zbl 1013.65033 [8] T. Davis, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it 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, {\it Block LU factorization}, Numer. Linear Algebra Appl., 2 (1995), pp. 173-190. · Zbl 0834.65010 [15] L. Foster, {\it San Jose State University Singular Matrix Database}, . [16] A. George, {\it 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, {\it 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, {\it 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, {\it Separators and structure prediction in sparse orthogonal factorization}, Linear Algebra Appl., 262 (1997). · Zbl 0881.15015 [20] G. H. Golub, {\it 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, {\it Matrix Computations}, 4th ed., The Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037 [22] Z. N. Goreinov SA, Tyrtyshnikov EE, {\it A theory of pseudoskeleton approximations}, Linear Algebra Appl., 261 (1997), pp. 1-21. · Zbl 0877.65021 [23] L. Grigori, S. Cayrols, and J. Demmel, {\it 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, {\it 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, {\it 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, {\it 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, {\it Regularization tools version 4.1 for MATLAB 7.3}. [28] Y. P. Hong and C.-T. Pan, {\it 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, {\it 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, {\it 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, {\it A separator theorem for planar graphs}, SIAM J. Appl. Math., 36 (1979), pp. 177-189. · Zbl 0432.05022 [32] M. W. Mahoney, {\it Randomized algorithms for matrices and data}, Found. Trends Mach. Learn., 3 (2011), pp. 123-224. · Zbl 1232.68173 [33] L. Miranian and M. Gu, {\it Strong rank revealing LU factorizations}, Linear Algebra Appl., (2003), pp. 1-16. · Zbl 1020.65016 [34] C.-T. Pan, {\it On the existence and computation of rank-revealing LU factorizations}, Linear Algebra Appl., 316 (2000), pp. 199-222. · Zbl 0962.65023 [35] Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, 2nd ed., SIAM, Philadelphia, 2011. · Zbl 1242.65068 [36] G. Stewart, {\it 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, {\it 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.