×

A Golub-Kahan Davidson method for accurately computing a few singular triplets of large sparse matrices. (English) Zbl 1420.65047

Summary: Obtaining high accuracy singular triplets for large sparse matrices is a significant challenge, especially when searching for the smallest triplets. Due to the difficulty and size of these problems, efficient methods must function iteratively, with preconditioners, and under strict memory constraints. In this research, we present a Golub-Kahan Davidson method (GKD), which satisfies these requirements and includes features such as soft-locking with orthogonality guarantees, an inner correction equation similar to Jacobi-Davidson, locally optimal \(+k\) restarting, and the ability to find real zero singular values in both square and rectangular matrices. Additionally, our method achieves full accuracy while avoiding the augmented matrix, which often converges slowly for the smallest triplets due to the difficulty of interior eigenvalue problems. We describe our method in detail, including implementation issues that arise. Our experimental results confirm the efficiency and stability of our method over the current implementation of PHSVDS in the PRIMME software package.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A04 Linear transformations, semilinear transformations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Advanced Micro Devices, Inc., AMD OpenCL Optimisation Guide, http://developer.amd.com/wordpress/media/2013/12/AMD_OpenCL_Programming_Optimization_Guide2.pdf (accessed 2018-02-14).
[2] O. Alter, P. O. Brown, and D. Botstein, Singular value decomposition for genome-wide expression data processing and modeling, Proc. Natl. Acad. Sci. USA, 97 (2000), pp. 10101-10106.
[3] J. Baglama, D. Calvetti, and L. Reichel, IRBL: An implicitly restarted block-Lanczos method for large-scale Hermitian eigenproblems, SIAM J. Sci. Comput., 24 (2003), pp. 1650-1677, https://doi.org/10.1137/S1064827501397949. · Zbl 1044.65027
[4] J. Baglama and L. Reichel, Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM J. Sci. Comput., 27 (2005), pp. 19-42, https://doi.org/10.1137/04060593X. · Zbl 1087.65039
[5] J. Baglama and L. Reichel, Restarted block Lanczos bidiagonalization methods, Numer. Algorithms, 43 (2006), pp. 251-272. · Zbl 1110.65027
[6] T. A. Davis and Y. Hu, The University of Florida sparse matrix collection, ACM Trans. Math. Software, 38 (2011), 1. · Zbl 1365.65123
[7] A. S. Gambhir, A. Stathopoulos, and K. Orginos, Deflation as a method of variance reduction for estimating the trace of a matrix inverse, SIAM J. Sci. Comput., 39 (2017), pp. A532-A558, https://doi.org/10.1137/16M1066361. · Zbl 1365.65111
[8] G. Golub and W. Kahan, Calculating the singular values and pseudo-inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), pp. 205-224. · Zbl 0194.18201
[9] G. H. Golub and C. F. Van Loan, Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009
[10] R. G. Grimes, J. G. Lewis, and H. D. Simon, A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 228-272, https://doi.org/10.1137/S0895479888151111. · Zbl 0803.65044
[11] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, Deep learning with limited numerical precision, in Proceedings of the International Conference on Machine Learning, 2015, pp. 1737-1746.
[12] M. E. Hochstenbach, A Jacobi-Davidson type SVD method, SIAM J. Sci. Comput., 23 (2001), pp. 606-628, https://doi.org/10.1137/S1064827500372973. · Zbl 1002.65048
[13] W. Hoffmann, Iterative algorithms for Gram-Schmidt orthogonalization, Computing, 41 (1989), pp. 335-348. · Zbl 0667.65037
[14] J. Huang and Z. Jia, On inner iterations of Jacobi-Davidson type methods for large SVD computations, SIAM J. Sci. Comput., 41 (2019), pp. A1574-A1603, https://doi.org/10.1137/18M1192019.
[15] Z. Jia and C. Li, Inner iterations in the shift-invert residual Arnoldi method and the Jacobi-Davidson method, Sci. China Math., 57 (2014), p. 1733-1752, https://doi.org/10.1007/s11425-014-4791-5. · Zbl 1312.65054
[16] Z. Jia and C. Li, Harmonic and refined harmonic shift-invert residual Arnoldi and Jacobi-Davidson methods for interior eigenvalue problems, J. Comput. Appl. Math., 282 (2015), pp. 83-97, https://doi.org/10.1016/j.cam.2014.12.043. · Zbl 1309.65041
[17] Z. Jia and D. Niu, An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 246-265, https://doi.org/10.1137/S0895479802404192. · Zbl 1063.65030
[18] I. Jolliffe, Principal Component Analysis, Springer-Verlag, New York, 2002.
[19] A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541, https://doi.org/10.1137/S1064827500366124. · Zbl 0992.65028
[20] R. M. Larsen, Lanczos bidiagonalization with partial reorthogonalization, DAIMI Report Series, 27 (1998), 537.
[21] Q. Liang and Q. Ye, Computing singular values of large matrices with an inverse-free preconditioned Krylov subspace method, Electron. Trans. Numer. Anal., 42 (2014), pp. 197-221. · Zbl 1312.65061
[22] S. Markidis, S. W. D. Chien, E. Laure, I. B. Peng, and J. S. Vetter, NVIDIA Tensor Core Programmability, Performance & Precision, preprint, https://arxiv.org/abs/1803.04014, 2018.
[23] J. R. McCombs and A. Stathopoulos, Iterative validation of eigensolvers: A scheme for improving the reliability of Hermitian eigenvalue solvers, SIAM J. Sci. Comput., 28 (2006), pp. 2337-2358, https://doi.org/10.1137/050627617. · Zbl 1126.65031
[24] K. Meerbergen, R. Morgan, and A. Knyazev, Inexact methods, in Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., SIAM, Philadelphia, 2000, pp. 337-368, https://doi.org/10.1137/1.9780898719581.ch11.
[25] Y. Notay, Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem, Numer. Linear Algebra Appl., 9 (2002), pp. 21-44. · Zbl 1071.65516
[26] S. Osiński, J. Stefanowski, and D. Weiss, Lingo: Search results clustering algorithm based on singular value decomposition, in Intelligent Information Processing and Web Mining, Springer, Berlin, Heidelberg, 2004, pp. 359-368.
[27] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980.
[28] H. Prasantha, H. Shashidhara, and K. B. Murthy, Image compression using SVD, in Proceedings of the IEEE International Conference on Computational Intelligence and Multimedia Applications, Vol. 3, 2007, pp. 143-145.
[29] H. D. Simon and H. Zha, Low-rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), pp. 2257-2274, https://doi.org/10.1137/S1064827597327309. · Zbl 0962.65038
[30] A. Stathopoulos, Locking Issues for Finding a Large Number of Eigenvectors of Hermitian Matrices, Tech. Report WM-CS-2005-09, Computer Science, The College of William & Mary, Williamsburg, VA, 2005.
[31] A. Stathopoulos, Nearly optimal preconditioned methods for Hermitian eigenproblems under limited memory. Part I: Seeking one eigenvalue, SIAM J. Sci. Comput., 29 (2007), pp. 481-514, https://doi.org/10.1137/050631574. · Zbl 1137.65019
[32] A. Stathopoulos and Y. Saad, Restarting techniques for (Jacobi-)Davidson symmetric eigenvalue methods, Electron. Trans. Numer. Anal., 7 (1998), pp. 163-181. · Zbl 0912.65027
[33] A. Stathopoulos and K. Wu, A block orthogonalization procedure with constant synchronization requirements, SIAM J. Sci. Comput., 23 (2002), pp. 2165-2182, https://doi.org/10.1137/S1064827500370883. · Zbl 1018.65050
[34] E. Vecharynski, Preconditioned Iterative Methods for Linear Systems, Eigenvalue and Singular Value Problems, Ph.D. thesis, University of Colorado at Denver, Denver, CO, 2011.
[35] K. Wu and H. Simon, Thick-restart Lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 602-616, https://doi.org/10.1137/S0895479898334605. · Zbl 0969.65030
[36] L. Wu, E. Romero, and A. Stathopoulos, PRIMME_SVDS: A High-Performance Preconditioned SVD Solver for Accurate Large-Scale Computations, preprint, https://arxiv.org/abs/1607.01404, 2016. · Zbl 1392.65100
[37] L. Wu and A. Stathopoulos, A preconditioned hybrid SVD method for accurately computing singular triplets of large matrices, SIAM J. Sci. Comput., 37 (2015), pp. S365-S388, https://doi.org/10.1137/140979381. · Zbl 1325.65055
[38] P. Zhang and Y. Gao, Matrix multiplication on high-density multi-GPU architectures: Theoretical and experimental investigations, in International Conference on High Performance Computing, Springer, Cham, 2015, pp. 17-30.
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.