×

Global convergence of the restarted Lanczos and Jacobi-Davidson methods for symmetric eigenvalue problems. (English) Zbl 1325.65050

Global convergence of the restarted Lanczos method in exact arithmetic using certain convergence properties of the Rayleigh-Ritz procedure, which can be obtained from the discussion in [M. Crouzeix et al., SIAM J. Sci. Comput. 15, No. 1, 62–76 (1994; Zbl 0803.65042)], is proved. For the restarted Lanczos method, Sorensen’s previous analysis establishes global convergence to the largest eigenvalues under the technical assumption that the absolute values of the off-diagonal elements of the Lanczos tridiagonal matrix are larger than a positive constant throughout the iterations. In this paper, global convergence without any such assumption is proved. The only assumption is that the initial vector is not orthogonal to any of the target exact eigenvectors. The convergence theorem is extended to the restarted Lanczos method for computing both the largest and smallest eigenvalues. Certain global convergence theorems of the block Lanczos and Jacobi-Davidson methods are also derived.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors

Citations:

Zbl 0803.65042
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baglama, J., Calvetti, D., Reichel, L.: Iterative methods for the computation of a few eigenvalues of a large symmetric matrix. BIT 36, 400-421 (1996) · Zbl 0856.65030
[2] Baglama, J., Calvetti, D., Reichel, L.: IRBL: an implicitly restarted block Lanczos method for largescale Hermitian eigenproblems. SIAM J. Sci. Comput. 24, 1650-1677 (2003) · Zbl 1044.65027
[3] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H.: Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia (2000) · Zbl 0965.65058
[4] Beattie, C., Embree, M., Rossi, J.: Convergence of restarted Krylov subspaces to invariant subspaces. SIAM J. Matrix Anal. Appl. 25, 1074-1109 (2004) · Zbl 1067.65037
[5] Beattie, C., Embree, M., Sorensen, D.C.: Convergence of polynomial restart Krylov methods for eigenvalue computations. SIAM Rev. 47, 492-515 (2005) · Zbl 1073.65028
[6] Calvetti, D., Reichel, L., Sorensen, D.C.: An implicitly restarted Lanczos method for large symmetric eigenvalue problems. Electron. Trans. Numer. Anal. 2, 1-21 (1994) · Zbl 0809.65030
[7] Crouzeix, M., Philippe, B., Sadkane, M.: The Davidson method. SIAM J. Sci. Comput. 15, 62-76 (1994) · Zbl 0803.65042
[8] Cullum, J.K.: The simultaneous computation of a few of the algebraically largest and smallest eigenvalues of a large, symmetric, sparse matrix. BIT 18, 265-275 (1978) · Zbl 0391.65013
[9] Cullum, J.K., Donath, W.E.: A block Lanczos algorithm for computing the \[q\] q algebraically largest eigenvalues and a corresponding eigenspace for large, sparse symmetric matrices. In: Proceedings of the 1994 IEEE Conference on Decision and Control, pp. 505-509 IEEE Press, Piscataway, NJ (1974) · Zbl 1078.65032
[10] Davidson, E.R.: The iterative calculation of a few of the lowest eigenvalues and corresponding eigenvectors of large real-symmetric matrices. J. Comput. Phys. 17, 87-94 (1975) · Zbl 0293.65022
[11] Demmel, J.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017
[12] Golub, GH; Underwood, R.; Rice, J. (ed.), The block Lanczos method for computing eigenvalues, 364-377 (1977), New York
[13] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edition. Johns Hopkins University (2013) · Zbl 1268.65037
[14] Hochstenbach, M.E., Sleijpen, G.L.G.: Two-sided and alternating Jacobi-Davidson. Linear Algebra Appl. 358, 145-172 (2003) · Zbl 1087.65035
[15] Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edition. Cambridge University (2012) · Zbl 0856.65030
[16] Karush, W.: An iterative method for finding characteristic vectors of a symmetric matrix. Pac. J. Math. 1, 233-248 (1951) · Zbl 0043.01602
[17] 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
[18] Knyazev, A.V., Skorokhodov, A.L.: On exact estimates of the convergence rate of the steepest ascent method in the symmetric eigenvalue problem. Linear Algebra Appl. 154-156, 245-257 (1991) · Zbl 0731.65023
[19] Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. J. Res. Nat. Bur. Stand. 45, 255-282 (1950)
[20] Li, R.C.: Sharpness in rates of convergence for the symmetric Lanczos method. Math. Comput. 79, 419-435 (2010) · Zbl 1206.65132
[21] Morgan, R.B., Scott, D.S.: Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices. SIAM J. Sci. Stat. Comput. 7, 817-825 (1986) · Zbl 0602.65020
[22] Notay, Y.: Is Jacobi-Davidson faster than Davidson? SIAM J. Matrix Anal. Appl. 26, 522-543 (2005) · Zbl 1078.65032
[23] Ovtchinnikov, E.: Convergence estimates for the generalized Davidson method for symmetric eigenvalue problems I: the preconditioning aspect. SIAM J. Numer. Anal. 41, 258-271 (2003) · Zbl 1078.65537
[24] Ovtchinnikov, E.: Convergence estimates for the generalized Davidson method for symmetric eigenvalue problems II: the preconditioning aspect. SIAM J. Numer. Anal. 41, 272-286 (2003) · Zbl 1078.65538
[25] Parlett, B.N.: The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs (1980) · Zbl 0431.65017
[26] Ruhe, A.: Implementation aspects of band Lanczos algorithms for computation of eigenvalues of large sparse symmetric matrices. Math. Comput. 33, 680-687 (1979) · Zbl 0443.65022
[27] Sleijpen, G.L.G., van der Vorst, A.: A Jacobi-Davidson iteration method for linear eigenvalue problems. SIAM J. Matrix Anal. Appl. 17, 401-425 (1996) · Zbl 0860.65023
[28] Sorensen, D.C.: Implicit application of polynomial filters in a \[k\] k-step Arnoldi method. SIAM J. Matrix Anal. Appl. 13, 357-385 (1992) · Zbl 0763.65025
[29] Stathopoulos, A.: Nearly optimal preconditioned methods for Hermitian eigenproblems under limited memory. Part I: seeking one eigenvalue. SIAM J. Sci. Comput. 29, 481-514 (2007) · Zbl 1137.65019
[30] Stathopoulos, A., Mccombs, J.R.: Nearly optimal preconditioned methods for Hermitian eigenproblems under limited memory. Part II: seeking many eigenvalues. SIAM J. Sci. Comput. 29, 2162-2188 (2007) · Zbl 1151.65320
[31] 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
[32] Yamazaki, I., Bai, Z., Simon, H.D., Wang, L.-W., Wu, K.: Adaptive projection subspace dimension for the thick-restart Lanczos method. ACM Trans. Math. Softw. 37, (2010) (Article No. 27). doi:10.1145/1824801.1824805 · Zbl 1364.65089
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.