Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Contour-Integral Based Method with Schur–Rayleigh–Ritz Procedure for Generalized Eigenvalue Problems

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

Recently, a class of eigensolvers based on contour integrals has been developed for computing the eigenvalues inside a given region in the complex plane. The CIRR method (a Rayleigh–Ritz type method with contour integrals) is a classic example among this kind of methods. It first constructs a subspace to contain the eigenspace of interest via a set of contour integrals, and then uses the standard Rayleigh–Ritz procedure to extract desired eigenpairs. However, it was shown that the CIRR method may fail to find the desired eigenpairs when the considered eigenproblem is non-Hermitian. This fact motivates us to develop a non-Hermitian scheme for the CIRR method. To this end, we formulate a Schur–Rayleigh–Ritz procedure to extract the desired eigenpairs. The theoretical analysis shows that our new extraction scheme can make the CIRR method also applicable for the non-Hermitian problems. Some implementation issues arising in practical applications are also studied. Numerical experiments are reported to illustrate the numerical performance of our new method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. http://math.nist.gov/MatrixMarket/.

References

  1. Ahlfors, L.: Complex Analysis, 3rd edn. McGraw-Hill, Inc., New York (1979)

    MATH  Google Scholar 

  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)

    Book  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Book  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  6. Beyn, W.-J.: An integral method for solving nonlinear eigenvalue problems. Linear Algebra Appl. 436, 3839–3863 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chan, T.T.: Rank revealing QR factorizations. Linear Algebra Appl. 88–89, 67–82 (1987)

    MathSciNet  MATH  Google Scholar 

  8. Davis, P.J., Rabinowitz, P.: Methods of Numerical Integration, 2nd edn. Academic Press, Orlando (1984)

    MATH  Google Scholar 

  9. Demmel, J.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997)

    Book  MATH  Google Scholar 

  10. Fang, H.-R., Saad, Y.: A filtered Lanczos procedure for extreme and interior eigenvalue problems. SIAM J. Sci. Comput. 34, A2220–A2246 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gallivan, K., Grimme, E., Van Dooren, P.: A rational Lanczos algorithm for model reduction. Numer. Algorithms. 12, 33–64 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  15. Ikegami, T., Sakurai, T.: Contour integral eigensolver for non-Hermitian systems: a Rayleigh–Ritz-type approach. Taiwan. J. Math. 14, 825–837 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  19. Moler, C.B., Stewart, G.W.: An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10, 241–256 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  20. Polizzi, E.: Density-matrix-based algorithm for solving eigenvalue problems. Phys. Rev. B 79, 115112 (2009)

    Article  Google Scholar 

  21. Ruhe, A.: Rational Krylov: a practical algorithm for large sparse nonsymmetric matrix pencils. SIAM J. Sci. Comput. 19, 1535–1551 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  22. Saad, Y.: Numerical Methods for Large Eigenvalue Problems. SIAM, Philadelphia (2011)

    Book  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  24. Sakurai, T., Sugiura, H.: A projection method for generalized eigenvalue problems using numerical integration. J. Comput. Appl. Math. 159, 119–128 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  27. Stewart, G.W.: Matrix Algorithms, Vol. II, Eigensystems. SIAM, Philadelphia (2001)

    Book  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  29. Van Barel, M.: Designing rational filter functions for solving eigenvalue problems by contour integration. Linear Algebra Appl. 502, 346–365 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  30. Van Barel, M., Kravanja, P.: Nonlinear eigenvalue problems and contour integrals. J. Comput. Appl. Math. 292, 526–540 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

I would like to thank Professor Michiel E. Hochstenbach for his careful reading of the paper, and for comments which have helped to substantially improve the presentation. This work was supported by the National Natural Science Foundation of China (NSFC) under Grant 11701593.

Author information

Authors and Affiliations

  1. School of Mathematics, Sun Yat-sen University, Guangzhou, People’s Republic of China

    Guojian Yin

Authors
  1. Guojian Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Guojian Yin.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yin, G. A Contour-Integral Based Method with Schur–Rayleigh–Ritz Procedure for Generalized Eigenvalue Problems. J Sci Comput 81, 252–270 (2019). https://doi.org/10.1007/s10915-019-01014-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10915-019-01014-0

Keywords

Mathematics Subject Classification

Search

Navigation