On Chebyshev-Davidson method for symmetric generalized eigenvalue problems. (English) Zbl 1458.65040

Summary: As we know, polynomial filtering technique is efficient for accelerating convergence of standard eigenvalue problems, which, however, has not appeared for solving generalized eigenvalue problems. In this paper, by integrating the effectiveness and robustness of the Chebyshev polynomial filters, we propose the Chebyshev-Davidson method for computing some extreme eigenvalues and corresponding eigenvectors of generalized matrix pencils. In this method, both matrix factorizations and solving systems of linear equations are all avoided. Convergence analysis indicates that the Chebyshev-Davidson method achieves quadratic convergence locally in an ideal situation. Furthermore, numerical experiments are carried out to demonstrate the convergence properties and to show great superiority and robustness over some state-of-the art iteration methods.


65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Full Text: DOI


[1] Anderson, CR, A Rayleigh-Chebyshev procedure for finding the smallest eigenvalues and associated eigenvectors of large sparse Hermitian matrices, J. Comput. Phys., 229, 7477-7487 (2010) · Zbl 1197.65034
[2] Banerjee, AS; Lin, L.; Hu, W.; Yang, C.; Pask, JE, Chebyshev polynomial filtered subspace iteration in the discontinuous Galerkin method for large-scale electronic structure calculations, J. Chem. Phys., 15, 154101 (2016)
[3] Bekas, C.; Kokiopoulou, E.; Saad, Y., Computation of large invariant subspaces using polynomial filtered Lanczos iterations with applications in density functional theory, SIAM J. Matrix Anal. Appl., 30, 397-418 (2008) · Zbl 1159.65319
[4] Bradbury, WW; Fletcher, R., New iterative methods for solution of the eigenproblem, Numer. Math., 9, 259-267 (1996) · Zbl 0202.43502
[5] Calvetti, D.; Reichel, L.; Sorensen, DC, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron. Trans. Numer. Anal., 2, 1-21 (1994) · Zbl 0809.65030
[6] Davidson, ER, 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
[7] Fang, HR; Saad, Y., A filtered Lanczos procedure for extreme and interior eigenvalue problems, SIAM J. Sci. Comput., 34, A2220-A2246 (2012) · Zbl 1253.65053
[8] Fokkema, DR; Sleijpen, GLG; van der Vorst, HA, Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils, SIAM J. Sci. Comput., 20, 94-125 (1998) · Zbl 0924.65027
[9] Golub, GH; Ye, Q., An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Copmut., 24, 312-334 (2002) · Zbl 1016.65017
[10] Guttel, S.; Polizzi, E.; Tang, PTP; Viaud, G., Zolotarev quadrature rules and load balancing for the FEAST eigensolver, SIAM J. Sci. Copmut., 37, A2100-A2122 (2015) · Zbl 1321.65055
[11] Hestenes, MR; Karush, W., A method of gradients for the calculation of the characteristic roots and vectors of a real symmetric matrix, J. Res. Nat. Bur. Stand., 47, 45-61 (1951)
[12] Ikegami, T.; Sakurai, T.; Nagashima, U., A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method, J. Comput. Appl. Math., 233, 1927-1936 (2010) · Zbl 1185.65061
[13] Imakura, A.; Du, L.; Sakurai, T., Error bounds of Rayleigh-Ritz type contour integral-based eigensolver for solving generalized eigenvalue problems, Numer. Algorithms, 71, 103-120 (2016) · Zbl 1333.65039
[14] Knyazev, AV, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23, 517-541 (2001) · Zbl 0992.65028
[15] Li, R-P; Xi, Y-Z; Vecharynski, E.; Yang, C.; Saad, Y., A thick-restart Lanczos algorithm with polynomial filtering for Hermitian eigenvalue problems, SIAM J. Sci. Comput., 38, A2512-A2534 (2016) · Zbl 1348.65071
[16] Li, Y.-Z., Yang, H.-Z.: Spectrum slicing for sparse Hermitian definite matrices based on Zolotarev’s functions. arxiv:1701.08935
[17] Miao, C-Q, Filtered Krylov-like sequence method for symmetric eigenvalue problems, Numer. Algorithms, 82, 791-807 (2019) · Zbl 1436.65039
[18] Morgan, RB, Generalizations of Davidson’s method for computing eigenvalues of large nonsymmetric matrices, J. Comput. Phys., 101, 287-291 (1992) · Zbl 0757.65046
[19] Morgan, RB; Scott, DS, Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices, SIAM J. Sci. Stat. Comput., 7, 817-825 (1986) · Zbl 0602.65020
[20] Morgan, RB; Scott, DS, Preconditioning the Lanczos algorithm for sparse symmetric eigenvalue problems, SIAM J. Sci. Comput., 14, 585-593 (1993) · Zbl 0791.65022
[21] Nakatsukasa, Y.; Freund, RW, Computing fundamental matrix decompositions accurately via the matrix sign function in two iterations: the power of Zolotarev’s functions, SIAM Rev., 58, 461-493 (2016) · Zbl 1383.15012
[22] Parlett, BN, The Symmetric Eigenvalue Problem (1998), Philadelphia: SIAM, Philadelphia
[23] Saad, Y., Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems, Math. Comput., 42, 567-588 (1984) · Zbl 0539.65013
[24] Saad, Y., Numerical Methods for Large Eigenvalue Problems (2011), Philadelphia: SIAM, Philadelphia · Zbl 1242.65068
[25] Sadkane, M., A block Arnoldi-Chebyshev method for computing the leading eigenpairs of large sparse unsymmetric matrices, Numer. Math., 64, 181-193 (1993) · Zbl 0791.65020
[26] Sakurai, T.; Sugiura, H., A projection method for generalized eigenvalue problems using numerical integration, J. Comput. Appl. Math., 159, 119-128 (2003) · Zbl 1037.65040
[27] Sleijpen, GLG; Booten, AGL; Fokkema, DR; van der Vorst, HA, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT Numer. Math., 36, 595-633 (1996) · Zbl 0861.65035
[28] Sleijpen, GLG; van der Vorst, HA, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl., 17, 401-425 (1996) · Zbl 0860.65023
[29] Sorensen, DC, Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13, 357-385 (1992) · Zbl 0763.65025
[30] Tang, PTP; Polizzi, E., FEAST as a subspace iteration eigensolver accelerated by approximate spectral projection, SIAM J. Matrix Anal. Appl., 35, 354-390 (2014) · Zbl 1303.65018
[31] Vecharynski, E.; Yang, C.; Pask, JE, A projected preconditioned conjugate gradient algorithm for computing many extreme eigenpairs of a Hermitian matrix, J. Comput. Phys., 290, 73-89 (2015) · Zbl 1349.65133
[32] Xi, Y-Z; Saad, Y., Computing partial spectra with least-squares rational filters, SIAM J. Sci. Comput., 38, A3020-A3045 (2016) · Zbl 1351.65026
[33] Zhou, Y-K, A block Chebyshev-Davidson method with inner-outer restart for large eigenvalue problems, J. Comput. Phys., 229, 9188-9200 (2010) · Zbl 1203.65077
[34] Zhou, Y-K; Saad, Y., A Chebyshev-Davidson algorithm for large symmetric eigenproblems, SIAM J. Matrix Anal. Appl., 29, 954-971 (2007) · Zbl 1151.65321
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.