×

Feast eigensolver for non-Hermitian problems. (English) Zbl 1352.65119

Summary: A detailed new upgrade of the FEAST eigensolver targeting non-Hermitian eigenvalue problems is presented and thoroughly discussed. It aims at broadening the class of eigenproblems that can be addressed within the framework of the FEAST algorithm. The algorithm is ideally suited for computing selected interior eigenvalues and their associated right/left biorthogonal eigenvectors located within a subset of the complex plane. It combines subspace iteration with efficient contour integration techniques that approximate the left and right spectral projectors. We discuss the various algorithmic choices that have been made to improve the stability and usability of the new non-Hermitian eigensolver. The latter retains the convergence property and multilevel parallelism of Hermitian FEAST, making it a valuable new software tool for the scientific community.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65Y05 Parallel numerical computation
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammerling, A. McKenney, et al., {\it LAPACK Users’ Guide}, Software Environ. Tools 9, SIAM, Philadelphia, 1999. · Zbl 0934.65030
[2] A. P. Austin and L. N. Trefethen, {\it Computing eigenvalues of real symmetric matrices with rational filters in real arithmetic}, SIAM J. Sci. Comput., 37 (2015), pp. A1365-A1387, . · Zbl 1328.15016
[3] Z. Bai, D. Day, J. Demmel, and J. Dongarra, {\it A Test Matrix Collection for Non-Hermitian Eigenvalue Problems}, , 1996.
[4] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., {\it Templates for the Solution of Algebraic Eigenvalue Problems}, Software Environ. Tools 11, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[5] C. G. Baker, U. L. Hetmaniuk, R. B. Lehoucq, and H. K. Thornquist, {\it Anasazi software for the numerical solution of large-scale eigenvalue problems}, ACM Trans. Math. Softw., 36 (2009), 13, . · Zbl 1364.65083
[6] S. Birner, T. Zibold, T. Andlauer, T. Kubis, M. Sabathil, A. Trellakis, and P. Vogl, {\it Nextnano: General purpose \(3\)-d simulations}, IEEE Trans. Electron. Devices, 54 (2007), pp. 2137-2142, .
[7] R. F. Boisvert, R. Pozo, K. Remington, R. F. Barrett, and J. J. Dongarra, {\it Matrix market: A web resource for test matrix collections}, in Proceedings of the IFIP TC2/WG2.5 Working Conference on Quality of Numerical Software: Assessment and Enhancement, Chapman & Hall, London, 1997, pp. 125-137, .
[8] M. Bollhoefer and Y. Notay, {\it JADAMILU: A software code for computing selected eigenvalues of large sparse symmetric matrices}, Comput. Phys. Commun., 177 (2007), pp. 951-964, . · Zbl 1196.65072
[9] A. Cerioni, L. Genovese, I. Duchemin, and T. Deutsch, {\it Accurate complex scaling of three dimensional numerical potentials}, J. Chem. Phys., 138 (2013), 204111, .
[10] S. Cooke, A. Mondelli, E. Nelson, and B. Levush, {\it Improved Jacobi-Davidson algorithm applied to non-Hermitian electromagnetic eigenvalue problems}, in 26th IEEE International Conference on Plasma Science, ICOPS ’99. IEEE Conference Record - Abstracts, 1999, 147, .
[11] E. Di Napoli, E. Polizzi, and Y. Saad, {\it Efficient Estimation of Eigenvalue Counts in an Interval}, preprint, , 2013, Numer. Linear Algebra Appl., submitted. · Zbl 1413.65092
[12] J. Dongarra, {\it Freely Available Software for Linear Algebra}, , 2015.
[13] M. Embree and L. N. Trefethen, {\it Pseudospectra Gateway}, .
[14] D. R. Fokkema, G. Sleijpen, and H. A. Van der Vorst, {\it Jacobi-Davidson style QR and QZ algorithms for the reduction of matrix pencils}, SIAM J. Sci. Comput., 20 (1998), pp. 94-125, . · Zbl 0924.65027
[15] Y. Futamura and T. Sakurai, {\it zPARES parallel eigenvalue solver}, http://zpares.cs.tsukuba.ac.jp/, 2014-2015.
[16] M. Galgon, L. Krämer, and B. Lang, {\it The FEAST algorithm for large eigenvalue problems}, Proc. Appl. Math. Mech., 11 (2011), pp. 747-748, .
[17] M. Galgon, L. Krämer, and B. Lang, {\it Counting eigenvalues and improving the integration in the feast algorithm}, Preprint BUW-IMACM, 12 (2012), 22.
[18] L. Genovese, B. Videau, M. Ospici, T. Deutsch, S. Goedecker, and J. Méhautois, {\it Daubechies wavelets for high performance electronic structure calculations: The bigdft project}, High Performance Computing, 339 (2011), pp. 149-164, . · Zbl 1221.82009
[19] G. H. Golub and C. F. Van Loan, {\it Matrix Computations}, Vol. 3, The Johns Hopkins University Press, Baltimore, 2012. · Zbl 1268.65037
[20] S. Güttel, E. Polizzi, P. T. P. Tang, and G. Viaud, {\it Zolotarev quadrature rules and load balancing for the feast eigensolver}, SIAM J. Sci. Comput., 37 (2015), pp. A2100-A2122, . · Zbl 1321.65055
[21] V. Hernandez, J. E. Roman, A. Tomas, and V. Vidal, {\it A Survey of Software for Sparse Eigenvalue Problems}, Tech. report STR-6, Universitat Politecnica de Valencia, Valencia, Spain, 2005, available online at .
[22] V. Hernandez, J. E. Roman, and V. Vidal, {\it SLEPc: A scalable and flexible toolkit for the solution of eigenvalue problems}, ACM Trans. Math. Software, 31 (2005), pp. 351-362, . · Zbl 1136.65315
[23] N. J. Higham, {\it Functions of Matrices: Theory and Computation}, SIAM, Philadelphia, 2008, . · Zbl 1167.15001
[24] T. Ikegami and T. Sakurai, {\it Contour integral eigensolver for non-Hermitian systems: A Rayleigh-Ritz-type approach}, Taiwanese J. Math., 14 (2010), pp. 825-837. · Zbl 1198.65071
[25] T. Ikegami, T. Sakurai, and U. Nagashima, {\it A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method}, J. Comput. Appl. Math., 233 (2010), pp. 1927-1936, . · Zbl 1185.65061
[26] J. Kestyn, V. Kalantzis, E. Polizzi, and Y. Saad, {\it PFEAST: A high performance sparse eigenvalue solver using distributed-memory linear system solvers}, in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ACM, New York, 2016, in press.
[27] A. V. Knyazev, {\it Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method}, SIAM J. Sci. Comput., 23 (2001), pp. 517-541 . · Zbl 0992.65028
[28] A. V. Knyazev, M. E. Argentati, I. Lashuk, and E. E. Ovtchinnikov, {\it Block locally optimal preconditioned eigenvalue xolvers BLOPEX in HYPRE and PETSc}, SIAM J. Sci. Comput., 29 (2007), pp. 2224-2239, . · Zbl 1149.65026
[29] S. E. Laux, {\it Solving complex band structure problems with the FEAST eigenvalue algorithm}, Phys. Rev. B, 86 (2012), 075103, .
[30] R. B. Lehoucq and J. A. Scott, {\it An Evaluation of Software for Computing Eigenvalues of Sparse Nonsymmetric Matrices}, Technical report MCS-P547-1195, Argonne National Laboratory, Lemont, IL, 1996.
[31] R. B. Lehoucq and D. C. Sorensen, {\it Deflation techniques for an implicitly restarted Arnoldi iteration}, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 789-821, . · Zbl 0863.65016
[32] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK Users’ Guide: Solution of Large-scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, Software Environ. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[33] K. Mendiratta and E. Polizzi, {\it A threaded SPIKE algorithm for solving general banded systems}, Parallel Comput., 37 (2011), pp. 733-741, .
[34] C. B. Moler and G. W. Stewart, {\it An algorithm for generalized matrix eigenvalue problems}, SIAM J. Numer. Anal., 10 (1973), pp. 241-256, . · Zbl 0253.65019
[35] A. Murakami, {\it A filter diagonalization method by the linear combination of resolvents}, IPSJ Trans. Adv. Comput. Syst., 49 (2008), pp. 66-87.
[36] A. Murakami, {\it A filter diagonalization method by the linear combination of resolvents}, IPSJ SIG Technical report 43 (2008-HPC-115), Information Processing Society of Japan, Tokyo, Japan, 2008.
[37] B. A. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[38] E. Polizzi, {\it Density-matrix-based algorithm for solving eigenvalue problems}, Phys. Rev. B, 79 (2009), 115112, .
[39] E. Polizzi and J. Kestyn, {\it A High-performance Numerical Library for Solving Eigenvalue Problems: FEAST Solver v 3.0 User’s Guide}, preprint, , 2015.
[40] QuantumWise, {\it Atomistix toolkit version 13.8.1}, .
[41] A. Ruhe, {\it Rational Krylov: A practical algorithm for large sparse nonsymmetric matrix pencils}, SIAM J. Sci. Comput., 19 (1998), pp. 1535-1551, . · Zbl 0914.65036
[42] Y. Saad, {\it Numerical solution of large nonsymmetric eigenvalue problems}, Comput. Phys. Commun., 53 (1989), pp. 71-90, . · Zbl 0798.65053
[43] Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, Vol. 158, SIAM, Philadelphia, 1992. · Zbl 0991.65039
[44] T. Sakurai and H. Sugiura, {\it A projection method for generalized eigenvalue problems using numerical integration}, J. Comput. Appl. Math., 159 (2003), pp. 119-128, . · Zbl 1037.65040
[45] T. Sakurai and H. Tadano, {\it CIRR: A Rayleigh-Ritz type method with contour integral for generalized eigenvalue problems}, Hokkaido Math. J., 36 (2007), pp. 745-757, . · Zbl 1156.65035
[46] O. Schenk and K. Gärtner, {\it On fast factorization pivoting methods for sparse symmetric indefinite systems}, Electronic Trans. Numer. Anal., 23 (2006), pp. 158-179. · Zbl 1112.65022
[47] G. Sleijpen and H. A. Van der Vorst, {\it A Jacobi-Davidson iteration method for linear eigenvalue problems}, SIAM Rev., 42 (2000), pp. 267-293, . · Zbl 0949.65028
[48] D. C. Sorensen, {\it Implicit application of polynomial filters in ak-step Arnoldi method}, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 357-385, . · Zbl 0763.65025
[49] A. Stathopoulos and J. R. McCombs, {\it PRIMME: Preconditioned iterative multimethod eigensolver: Methods and software description}, ACM Trans. Math. Softw., 37 (2010), 21, . · Zbl 1364.65087
[50] G. Stewart, {\it A Krylov-Schur algorithm for large eigenproblems}, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 601-614, . · Zbl 1003.65045
[51] P. T. P. Tang, J. Kestyn, and E. Polizzi, {\it A new highly parallel non-Hermitian eigensolver}, in Proceedings of the High Performance Computing Symposium, San Diego, 2014, article 1.
[52] P. T. P. Tang and E. Polizzi, {\it FEAST as a subspace iteration eigensolver accelerated by approximate spectral projection}, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 354-390, . · Zbl 1303.65018
[53] J. Towns, T. Cockerill, M. Dahan, I. Foster, K. Gaither, A. Grimshaw, V. Hazlewood, S. Lathrop, D. Lifka, G. D. Peterson, R. Roskies, J. R. Scott, and N. Wilkins-Diehr, {\it Xsede: Accelerating scientific discovery}, Comput. Sci. Eng., 16 (2014), pp. 62-74, .
[54] L. N. Trefethen, {\it Pseudospectra of Matrices}, Computing Laboratory Numerical Analysis Group, Oxford University, Oxford, 1991. · Zbl 0798.15005
[55] L. N. Trefethen and J. A. C. Weideman, {\it The exponentially convergent trapezoidal rule}, SIAM Rev., 56 (2014), pp. 385-458, . · Zbl 1307.65031
[56] K. Wu and H. Simon, {\it Thick-restart Lanczos method for large symmetric eigenvalue problems}, SIAM J. Matrix Anal. Appl., 22 (2000), pp. 602-616, . · Zbl 0969.65030
[57] G. Yin, R. H. Chan, and M. Yeung, {\it A FEAST Algorithm for Generalized Non-Hermitian Eigenvalue Problems}, preprint, , 2014.
[58] E. I. Zolotarev, {\it Application of elliptic functions to questions of functions deviating least and most from zero}, Zap. Imp. Akad. Nauk. St. Petersburg, 30 (1877), pp. 1-59.
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.