×

zbMATH — the first resource for mathematics

Computing the smallest singular triplets of a large matrix. (English) Zbl 1452.65065
Summary: In this paper we present a new type of restarted Krylov methods for calculating the smallest singular triplets of a large sparse matrix, \(A\). The new framework avoids the Lanczos bidiagonalization process and the use of polynomial filtering. This simplifies the restarting mechanism and allows the introduction of several modifications. Convergence is assured by a monotonicity property that pushes the computed Ritz values toward their limits.
Other innovations regard the construction of improved Krylov subspaces, which are generated by \((A^TA)^{-1}\), the inverse of the cross-product matrix, or by approximation of this matrix. The approximate inverse is computed by applying an iterative method to solve the related linear system. Numerical experiments illustrate the usefulness of the proposed approach.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F25 Orthogonalization in numerical linear algebra
65F50 Computational methods for sparse matrices
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Axelsson, O., Iterative solution methods (1994), University Press: University Press Cambridge · Zbl 0795.65014
[2] Baglama, J.; Calvetti, D.; Reichel, L., IRBL: an implicitly restarted block Lanczos method for large-scale Hermitian eigenproblems, SIAM J Sci Comput, 24, 1650-1677 (2003) · Zbl 1044.65027
[3] Baglama, J.; Reichel, L., Augmented implicitly restarted Lanczos bidiagonalization methods, SIAM J Sci Comput, 27, 19-42 (2005) · Zbl 1087.65039
[4] Baglama, J.; Reichel, L., Restarted block Lanczos bidiagonalization methods, Numer Algorithm, 43, 251-272 (2006) · Zbl 1110.65027
[5] Baglama, J.; Reichel, L., An implicitly restarted block Lanczos bidiagonalization method, using Leja shifts, BIT Numerical Mathematics, 64, 263-293 (2013) · Zbl 1269.65038
[6] Bai, A.; Demmel, J.; Dongarra, J.; Ruhe, A.; van der Vorst, H., Templates for the solution of algebraic eigenvalue problems: a practical guide (1999), SIAM: SIAM Philadelphia, PA
[7] Bekas, C.; Saad, Y., Computation of smallest eigenvalues using spectral Schur complements, SISC, 27, 458-481 (2005) · Zbl 1091.65035
[8] Berns-Müller, J.; Graham, I. G.; Spence, A., Inexact inverse iteration for symmetric matrices, Linear Algebra Appl, 416, 389-413 (2006) · Zbl 1101.65037
[9] Bjorck, A., Numerical methods for least-squares problems (1996), SIAM: SIAM Philadelphia · Zbl 0847.65023
[10] Calvetti, D.; Reichel, L.; Sorenson, D. C., An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron Trans Numer Anal, 2, 1-21 (1994) · Zbl 0809.65030
[11] Dax, A., On extremum properties of orthogonal quotient matrices, Linear Algebra Appl, 432, 1234-1257 (2010) · Zbl 1189.65067
[12] Dax, A., A cross-product approach for low-rank approximations of large matrices, Tech. Rep (2017), Hydrological Service of Israel
[13] Dax, A., A restarted Krylov method with inexact inversions, Num, Lin. Alg. with Applic, 26 (2019) · Zbl 07031713
[14] Dembo, R. S.; Eisenstat, S.; Steihaug, T., Inexact Newton methods, SIAM J Numer Anal, 19, 400-408 (1982) · Zbl 0478.65030
[15] Demmel, J. W., Applied numerical linear algebra (1997), SIAM: SIAM Philadelphia · Zbl 0879.65017
[16] Dongarra, J. J.; Duff, I. S.; Sorensen, D. C.; ven der Vorst, H. A., Numerical linear algebra for high-Performance computers (1998), SIAM: SIAM Philadelphia, PA · Zbl 0914.65014
[17] Duff, I. S.; Erisman, A. M.; Reid, J. K., Direct methods for sparse matrices (1986), Oxford University Press: Oxford University Press London · Zbl 0604.65011
[18] Freitag, M. A., Inner-outer iterative methods for eigenvalue problems - convergence and preconditioning (2007), Department of Mathematical Sciences, University of Bath, Ph.D. Thesis
[19] Freitag, M. A.; Spence, A., A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems, IMA J Numer Anal, 28, 522-551 (2008) · Zbl 1151.65030
[20] Freitag, M. A.; Spence, A., Rayleigh quotient iteration and simplified Jacobi-Davidson method with preconditioned iterative solves, Linear Algebra Appl, 428, 2049-2060 (2008) · Zbl 1142.65034
[21] Freitag, M. A.; Spence, A., Shift-invert Arnoldi’s method with preconditioned iterative solves, SIAM J Matrix Anal Appl, 31, 942-969 (2009) · Zbl 1204.65034
[22] Giladi, E.; Golub, G. H.; Keller, J. B., Inner and outer iterations for the Chebyshev algorithm, SIAM J Numer Anal, 35, 300-319 (1998) · Zbl 0911.65024
[23] Golub, G. H.; Van Loan, C. F., Matrix computations (2013), Johns Hopkins Univ. Press · Zbl 1268.65037
[24] Golub, G. H.; Ye, Q., Inexact inverse iteration for generalized eigenvalue problems, BIT, 40, 671-684 (2000) · Zbl 0984.65032
[25] Golub, G. H.; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J Sci Comput, 24, 312-334 (2002) · Zbl 1016.65017
[26] Golub, G. H.; Zhang, Z.; Zha, H., Large sparse symmetric eigenvalue problems with homogeneous linear constraints: the Lanczos process with inner-outer iterations, Linear Algebra Appl, 309, 289-306 (2000) · Zbl 0948.65033
[27] Greenbaum, A., Iterative methods for solving linear systems (1997), SIAM: SIAM Philadelphia · Zbl 0883.65022
[28] Horn, R. A.; Johnson, C. R., Matrix analysis (1985), Cambridge University Press · Zbl 0576.15001
[29] Jia, Z., The convergence of harmonic Ritz values, harmonic Ritza vectors and refined harmonic Ritz vectors, Math Comput, 74, 1441-1456 (2005) · Zbl 1072.65051
[30] Jia, Z.; Niu, D., An implicitly restarted refined bidiagonalization Lanczos method for compting a partial singular value decomposition, SIAM J Matrix Anal Appl, 25, 246-265 (2003) · Zbl 1063.65030
[31] Z. Jia and D. Niu, A refined harmonic Lanczos bidiagonalization method and an implicitly restarted algorithm for computing the smallest singular triplets of large matrices, SIAM J Sci Comput 32 (1010, 714-744. · Zbl 1215.65072
[32] Kokiopoulou, E.; Bekas, C.; Gallopoulos, E., Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization, Appl Numer Math, 49, 39-61 (2004) · Zbl 1049.65027
[33] Knyazev, A. V., Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J Sci Comput, 23, 517-541 (2001) · Zbl 0992.65028
[34] Knyazev, A. V.; Argentati, M. E.; Lashuk, I.; Ovtchinnikov, E. E., Block locally optimal preconditioned eigenvalue solvers (BLOPEX) in hypre and PETSc, SIAM J Sci Comput, 29 (2007), 2224-2007 · Zbl 1149.65026
[35] Lai, Y.-L.; Lin, K.-Y.; Lin, W.-W., An inexact inverse iteration for large sparse eigenvalue problems, Numer Lin Algebra Appl, 1, 1-13 (1997) · Zbl 0889.65038
[36] Larsen, R. M., Lanczos Bidiagonalization with Partial Reorthogonalization (1998), Dept. of Computer Science, University of Aarhus: Dept. of Computer Science, University of Aarhus Aarhus, Denmark, Ph.D. thesis
[37] Larsen, R. M., Combining implicit restarts and partial reorthogonalization in Lanczos bidiagonalization
[38] Li, R.; Xi, Y.; Vecharynski, E.; Yang, C.; Saad, Y., A thick-restart Lanczos algorithm with polynomial filtering for hermitian eigenvalue problems, SIAM J Sci Comput, 38, 2512-2534 (2016)
[39] Liang, Q.; Ye, Q., Computing singular values of large matrices with an inverse-free preconditioned Krylov subspace method, ETNA, 42, 197-221 (2014) · Zbl 1312.65061
[40] Morgan, R. B., On restarting the Arnoldi method for large non-symmetric eigenvalues problems, Math Comput, 65, 1213-1230 (1996) · Zbl 0857.65041
[41] Niu, D.; Yuan, X., A harmonic Lanczos bidiagonalization method for computing interior singular triplets of large matrices, Appl Math Comput, 218, 7459-7467 (2012) · Zbl 1246.65065
[42] Niu, D.; Yuan, X., An implicitly restarted Lanczos bidiagonalization method with refined harmonic shifts for computing smallest singular triplets, J Comput Appl Math, 260, 208-217 (2014) · Zbl 1293.65057
[43] Parlett, B. N., The symmetric eigenvalue problem (1980), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0431.65017
[44] Saad, Y., Iterative methods for sparse linear systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042
[45] Saad, Y., Numerical methods for large eigenvalue problems (2011), SIAM: SIAM Philadelphia · Zbl 1242.65068
[46] Simoncini, V.; Eldén, L., Inexact Rayleigh quotient-type methods for eigenvalue computations, BIT, 42, 159-182 (2002) · Zbl 1003.65033
[47] Simoncini, V.; Szyld, D. B., Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J on Sci Comput, 25, 454-477 (2003) · Zbl 1048.65032
[48] Sleijpen, G. L.G.; van der Vorst, H. A., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM Rev, 42 (2000), 267-239 · Zbl 0949.65028
[49] Smit, P.; Paardekooper, M. H.C., The effects on inexact solvers in algorithms for symmetric eigenvalue problems, Lin. Alg. Appl, 287, 337-357 (1999) · Zbl 0943.65048
[50] Sorensen, D. C., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J Matrix Anal Appl, 13, 357-385 (1992) · Zbl 0763.65025
[51] Stathopoulos, A.; McCombs, J. R., PRIMME: PReconditioned iterative MultiMethod eigensolver: methods and software description, ACM Trans Math Software, 37, 21-30 (2010) · Zbl 1364.65087
[52] Stewart, G. W., Matrix algorithms, vol. I (1998), Basic Decompositions, SIAM: Basic Decompositions, SIAM Philadelphia · Zbl 0910.65012
[53] Stewart, G. W., Matrix algorithms, vol. II (2001), Eigensystems, SIAM: Eigensystems, SIAM Philadelphia · Zbl 0984.65031
[54] Trefethen, L. N.; Bau, D., Numerical linear algebra (1997), SIAM: SIAM Philadelphia · Zbl 0874.65013
[55] van den Eshof, J.; Sleijpen, G. L.G., Inexact Krylov subspace methods for linear systems, SIAM J Matrix Anal Appl, 26, 125-153 (2004) · Zbl 1079.65036
[56] van der Vorst, H. A., Iterative Krylov methods for large linear systems (2003), Cambridge University Press · Zbl 1023.65027
[57] Varga, R. S., Matrix iterative analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602
[58] Watkins, D. S., The matrix eigenvalue problem: GR and Krylov subspace methods (2007), SIAM: SIAM Philadelphia · Zbl 1142.65038
[59] Wu, K.; Simon, H., Thick-restarted Lanczos method for large symmetric eigenvalue problems, SIAM J Matrix Anal Appl, 22, 602-616 (2000) · Zbl 0969.65030
[60] Wu, L.; Romero, E.; Stathopoulos, A., PRIMME svds: a high-performance preconditioned SVD solver for accurate large-scale computations, SIAM J Sci Comput, 39, 248-271 (2017)
[61] Wu, L.; Stathopoulos, A., A preconditioned hybrid SVD method for computing accurately singular triplets of large matrices, SIAM J Sci Comput, 37, 365-388 (2015) · Zbl 1325.65055
[62] Xue, F.; Elman, H. C., Convergence analysis of iterative solvers in inexact Rayleigh quotient iteration, SIAM J Matrix Anal Appl, 31, 877-899 (2009) · Zbl 1201.65060
[63] Xue, F.; Elman, H., Fast inexact subspace iteration for generalized eigenvalue problems with spectral tranformation, Linear Algebra Appl, 435, 601-622 (2011) · Zbl 1253.65059
[64] Xue, F.; Elman, H., Fast inexact implicitly restarted Arnoldi method for generalized eigenvalue problems with spectral transformation, SIAM J Matrix Anal Appl, 33, 433-459 (2012) · Zbl 1263.65041
[65] Yamazaki, I.; Bai, Z.; Simon, H.; Wang, L.; Wu, K., Adaptive projection subspace dimension for the thick-restart Lanczos method, ACM Trans Math Software, 47 (2010), Article No. 27 · Zbl 1364.65089
[66] Ye, Q.; Zhang, P., Inexact inverse subspace iteration for generalized eigenvalue problems, Linear Algebra and its Appl, 434, 1697-1715 (2011) · Zbl 1215.65069
[67] Young, D. M., Iterative solution of large linear systems (1971), Academic Press: Academic Press New York · Zbl 0231.65034
[68] Zhang, F., Matrix theory: basic results and techniques (1999), Springer-Verlag: Springer-Verlag New York · Zbl 0948.15001
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.