×

Krylov eigenvalue strategy using the FEAST algorithm with inexact system solves. (English) Zbl 1513.65096

Summary: The FEAST eigenvalue algorithm is a subspace iteration algorithm that uses contour integration to obtain the eigenvectors of a matrix for the eigenvalues that are located in any user-defined region in the complex plane. By computing small numbers of eigenvalues in specific regions of the complex plane, FEAST is able to naturally parallelize the solution of eigenvalue problems by solving for multiple eigenpairs simultaneously. The traditional FEAST algorithm is implemented by directly solving collections of shifted linear systems of equations; in this paper, we describe a variation of the FEAST algorithm that uses iterative Krylov subspace algorithms for solving the shifted linear systems inexactly. We show that this iterative FEAST algorithm (which we call IFEAST) is mathematically equivalent to a block Krylov subspace method for solving eigenvalue problems. By using Krylov subspaces indirectly through solving shifted linear systems, rather than directly using them in projecting the eigenvalue problem, it becomes possible to use IFEAST to solve eigenvalue problems using very large dimension Krylov subspaces without ever having to store a basis for those subspaces. IFEAST thus combines the flexibility and power of Krylov methods, requiring only matrix-vector multiplication for solving eigenvalue problems, with the natural parallelism of the traditional FEAST algorithm. We discuss the relationship between IFEAST and more traditional Krylov methods and provide numerical examples illustrating its behavior.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation

References:

[1] GolubGH, Van LoanCF. Matrix computations. vol. 3. Baltimore, MD: JHU Press; 2012.
[2] SaadY. Numerical methods for large eigenvalue problems: Revised edition. Philadelphia, PA: SIAM; 2011.
[3] PolizziE. Density‐matrix‐based algorithm for solving eigenvalue problems. Phys Rev B. 2009;79:115112.
[4] TangPTP, PolizziE. Feast as a subspace iteration eigensolver accelerated by approximate spectral projection. SIAM J Matrix Anal Appl. 2014;35(2):354-390. · Zbl 1303.65018
[5] KestynJ, PolizziE, Peter TangPT. FEAST eigensolver for non‐Hermitian problems. SIAM J Sci Comput. 2016;38(5):S772-S799. · Zbl 1352.65119
[6] TangPTP, KestynJ, PolizziE. A new highly parallel non‐Hermitian eigensolver. Proceedings of the High Performance Computing Symposium; 2014; Tampa, FL. San Diego, CA: Society for Computer Simulation International; 2014.
[7] ImakuraA, DuL, SakuraiT. A block Arnoldi‐type contour integral spectral projection method for solving generalized eigenvalue problems. Appl Math Lett. 2014;32:22-27. MR3182841. · Zbl 1311.65037
[8] SakuraiT, SugiuraH. A projection method for generalized eigenvalue problems using numerical integration. Proceedings of the 6th Japan‐China Joint Seminar on Numerical Mathematics; 2003; Tsukuba, Japan. p. 119-128. MR2022322. · Zbl 1037.65040
[9] SakuraiT, TadanoH. CIRR: a Rayleigh‐Ritz type method with contour integral for generalized eigenvalue problems. Hokkaido Math J. 2007;36(4):745-757. MR2378289. · Zbl 1156.65035
[10] GüttelS, PolizziE, TangPTP, ViaudG. Zolotarev quadrature rules and load balancing for the FEAST eigensolver. SIAM J Sci Comput. 2015;37(4):A2100-A2122. · Zbl 1321.65055
[11] WinkelmannJ, Di NapoliE. Non‐linear least‐squares optimization of rational filters for the solution of interior eigenvalue problems. arXiv preprint arXiv:1704.03255; 2017.
[12] XiY, SaadY. Computing partial spectra with least‐squares rational filters. SIAM J Sci Comput. 2016;38(5):A3020-A3045. · Zbl 1351.65026
[13] SchenkO, GärtnerK, KarypisG, RöllinS, HagemannM. PARDISO solver project. 2010. http://www.pardiso-project.org/
[14] KalantzisV, KestynJ, PolizziE, SaadY. Domain decomposition approaches for accelerating contour integration eigenvalue solvers for symmetric eigenvalue problems. preprint; 2016.
[15] GiannozziP, BaroniS, BoniniN, et al. QUANTUM ESPRESSO: a modular and open‐source software project for quantum simulations of materials. J Phys: Condens Matter. 2009;21(39):395502.
[16] Berns‐MüllerJ, GrahamIG, SpenceA. Inexact inverse iteration for symmetric matrices. Linear Algebra Appl. 2006;416(2‐3):389-413. · Zbl 1101.65037
[17] GolubGH, YeQ. Inexact inverse iteration for generalized eigenvalue problems. BIT Numer Math. 2000;40(4):671-684. · Zbl 0984.65032
[18] LaiY‐L, LinK‐Y, LinW‐W. An inexact inverse iteration for large sparse eigenvalue problems. Numer Linear Algebra Appl. 1997;4(5):425-437. · Zbl 0889.65038
[19] RobbéM, SadkaneM, SpenceA. Inexact inverse subspace iteration with preconditioning applied to non‐Hermitian eigenvalue problems. SIAM J Matrix Anal Appl. 2009;31(1):92-113. · Zbl 1269.65036
[20] PaigeCC, SaundersMA. Solution of sparse indefinite systems of linear equations. SIAM J Numer Anal. 1975;12(4):617-629. · Zbl 0319.65025
[21] FreundR. On conjugate gradient type methods and polynomial preconditioners for a class of complex non‐Hermitian matrices. Numer Math. 1990;57(1):285-312. · Zbl 0702.65034
[22] SaadY, SchultzMH. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J Sci Stat Comput. 1986;7(3):856-869. · Zbl 0599.65018
[23] SaadY. Analysis of subspace iteration for eigenvalue problems with evolving matrices. SIAM J Matrix Anal Appl. 2016;37(1):103-122.
[24] FreitagMA, SpenceA. A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems. IMA J Numer Anal. 2008;28(3):522-551. · Zbl 1151.65030
[25] FreitagMA, SpenceA, VainikkoE. Rayleigh quotient iteration and simplified Jacobi‐Davidson with preconditioned iterative solves for generalised eigenvalue problems. Bath, UK: Department of Mathematical Sciences, University of Bath; 2008.
[26] XueF, ElmanHC. Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation. Linear Algebra Appl. 2011;435(3):601-622. · Zbl 1253.65059
[27] YeQ, ZhangP. Inexact inverse subspace iteration for generalized eigenvalue problems. Linear Algebra Appl. 2011;434(7):1697-1715. · Zbl 1215.65069
[28] SaadY. Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math Comput. 1984;42(166):567-588. · Zbl 0539.65013
[29] SorensenDC. Implicit application of polynomial filters in a k‐step Arnoldi method. SIAM J Matrix Anal Appl. 1992;13(1):357-385. · Zbl 0763.65025
[30] SaadY. Iterative methods for sparse linear systems. Philadelphia, PA: SIAM; 2003. · Zbl 1031.65046
[31] MorganRB, ZengM. Harmonic projection methods for large non‐symmetric eigenvalue problems. Numer Linear Algebra Appl. 1998;5(1):33-55. · Zbl 0937.65045
[32] MorganRB. Computing interior eigenvalues of large matrices. Linear Algebra Appl. 1991;154-156:289-309. · Zbl 0734.65029
[33] DavisTA, HuY. The university of Florida sparse matrix collection. ACM Trans Math Softw. 2011;38(1). · Zbl 1365.65123
[34] LehoucgRB, SorensenDC, YangC. ARPACK user’s guide. Philadelphia: SIAM; 1998. http://www.caam.rice.edu/software/ARPACK/ · Zbl 0901.65021
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.