×

A contour-integral based method with Schur-Rayleigh-Ritz procedure for generalized eigenvalue problems. (English) Zbl 1444.65012

The author presents a contour-integral method related to the Schur-Rayleigh-Ritz procedure for computing eigenpairs inside a given region. The goal is to make the CIRR method also applicable for non-Hermitian problems. The proposed method, called CISRR, is based on the CIRR method. The main difference between both methods is the way of extracting the desired eigenpairs. The CIRR method extracts them from the subspace spanned by the corresponding eigenbasis, the new method from the subspace spanned by the corresponding right generalized Schur vectors. The extraction approach can circumvent the difficulties related to ill-conditioning or deficiency of the eigenbasis.
The numerical experiments show that the new method is more reliable and accurate than the CIRR method. In the present work, some implementation issues arising in practical applications are also studied. The new method performs better if the parameter \(\sigma\) is chosen as a value inside the target region. In this case, the extraction approach becomes the harmonic Schur-Rayleigh-Ritz procedure. It is easy to see that the new method can be used to retrieve the partial generalized Schur vectors.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F22 Ill-posedness and regularization problems in numerical linear algebra
15A18 Eigenvalues, singular values, and eigenvectors
58C40 Spectral theory; eigenvalue problems on manifolds

Software:

JDQZ; LAPACK; FEAST; JDQR; CIRR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlfors, L.: Complex Analysis, 3rd edn. McGraw-Hill, Inc., New York (1979) · Zbl 0395.30001
[2] Anderson, A., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. SIAM, Philadephia (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604
[3] Austin, A.P., Trefethen, L.N.: Computing eigenvalues of real symmetric matrices with rational filters in real arithmetic. SIAM J. Sci. Comput. 37, A1365-A1387 (2015) · Zbl 1328.15016 · doi:10.1137/140984129
[4] 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 · doi:10.1137/1.9780898719581
[5] Beckermann, B., Golub, G.H., Labahn, G.G.: On the numerical condition of a generalized Hankel eigenvalue problem. Numer. Math. 106, 41-68 (2007) · Zbl 1121.65036 · doi:10.1007/s00211-006-0054-x
[6] Beyn, W.-J.: An integral method for solving nonlinear eigenvalue problems. Linear Algebra Appl. 436, 3839-3863 (2012) · Zbl 1237.65035 · doi:10.1016/j.laa.2011.03.030
[7] Chan, T.T.: Rank revealing QR factorizations. Linear Algebra Appl. 88-89, 67-82 (1987) · Zbl 0624.65025
[8] Davis, P.J., Rabinowitz, P.: Methods of Numerical Integration, 2nd edn. Academic Press, Orlando (1984) · Zbl 0537.65020
[9] Demmel, J.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017 · doi:10.1137/1.9781611971446
[10] Fang, H.-R., Saad, Y.: A filtered Lanczos procedure for extreme and interior eigenvalue problems. SIAM J. Sci. Comput. 34, A2220-A2246 (2012) · Zbl 1253.65053 · doi:10.1137/110836535
[11] Fokkema, D.R., Sleijpen, G.L.G., Van Der Vorst, H.A.: Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils. SIAM J. Sci. Comput. 20, 94-125 (1998) · Zbl 0924.65027 · doi:10.1137/S1064827596300073
[12] Gallivan, K., Grimme, E., Van Dooren, P.: A rational Lanczos algorithm for model reduction. Numer. Algorithms. 12, 33-64 (1996) · Zbl 0870.65053 · doi:10.1007/BF02141740
[13] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[14] Güttel, S., Polizzi, E., Tang, P., Viaud, G.: Zolotarev quadrature rules and load balancing for the FEAST eigensolver. SIAM J. Matrix Anal. Appl. 37, A2100-A2122 (2015) · Zbl 1321.65055
[15] Ikegami, T., Sakurai, T.: Contour integral eigensolver for non-Hermitian systems: a Rayleigh-Ritz-type approach. Taiwan. J. Math. 14, 825-837 (2010) · Zbl 1198.65071 · doi:10.11650/twjm/1500405869
[16] 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 · doi:10.1016/j.cam.2009.09.029
[17] Imakura, A., Du, L., Sakurai, T.: Error bounds of Rayleigh-Ritz type contour integral-based eigensolver for solving generalized eigenvalue problems. Numer. Algorithms 68, 103-120 (2015) · Zbl 1333.65039
[18] Krämer, L., Di Napoli, E., Galgon, M., Lang, B., Bientinesi, P.: Dissecting the FEAST algorithm for generalized eigenproblems. J. Comput. Appl. Math. 244, 1-9 (2013) · Zbl 1260.65029 · doi:10.1016/j.cam.2012.11.014
[19] Moler, C.B., Stewart, G.W.: An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 241-256 (1973) · Zbl 0253.65019 · doi:10.1137/0710024
[20] Polizzi, E.: Density-matrix-based algorithm for solving eigenvalue problems. Phys. Rev. B 79, 115112 (2009) · doi:10.1103/PhysRevB.79.115112
[21] Ruhe, A.: Rational Krylov: a practical algorithm for large sparse nonsymmetric matrix pencils. SIAM J. Sci. Comput. 19, 1535-1551 (1998) · Zbl 0914.65036 · doi:10.1137/S1064827595285597
[22] Saad, Y.: Numerical Methods for Large Eigenvalue Problems. SIAM, Philadelphia (2011) · Zbl 1242.65068 · doi:10.1137/1.9781611970739
[23] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[24] 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 · doi:10.1016/S0377-0427(03)00565-X
[25] Sakurai, T., Tadano, H.: CIRR: a Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems. Hokkaido Math. J. 36, 745-757 (2007) · Zbl 1156.65035 · doi:10.14492/hokmj/1272848031
[26] Sakurai, T., Futamura, Y., Tadano, H.: Efficient parameter estimation and implementation of a contour integral-based eigensolver. J. Algorithms Comput. Technol. 7, 249-269 (2013) · doi:10.1260/1748-3018.7.3.249
[27] Stewart, G.W.: Matrix Algorithms, Vol. II, Eigensystems. SIAM, Philadelphia (2001) · Zbl 0984.65031 · doi:10.1137/1.9780898718058
[28] Tang, P., 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 · doi:10.1137/13090866X
[29] Van Barel, M.: Designing rational filter functions for solving eigenvalue problems by contour integration. Linear Algebra Appl. 502, 346-365 (2016) · Zbl 1386.65115 · doi:10.1016/j.laa.2015.05.029
[30] Van Barel, M., Kravanja, P.: Nonlinear eigenvalue problems and contour integrals. J. Comput. Appl. Math. 292, 526-540 (2015) · Zbl 1329.65109 · doi:10.1016/j.cam.2015.07.012
[31] Van der Vorst, H.A.: Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 13, 631-644 (1992) · Zbl 0761.65023 · doi:10.1137/0913035
[32] Vecharynski, E., Yang, C., Xue, F.: Generalized preconditioned locally harmonic residual method for non-Hermitian eigenproblems. SIAM J. Sci. Comput. 38, A500-A527 (2016) · Zbl 06548924 · doi:10.1137/15M1027413
[33] Yin, G., Chan, R., Yueng, M.-C.: A FEAST algorithm with oblique projection for generalized eigenvalue problems. Numer. Linear Algebra Appl. 24, e2092 (2017) · Zbl 1463.65078 · doi:10.1002/nla.2092
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.