×

Generalized preconditioned locally harmonic residual method for non-Hermitian eigenproblems. (English) Zbl 06548924

Summary: We introduce the generalized preconditioned locally harmonic residual (GPLHR) method for solving standard and generalized non-Hermitian eigenproblems. The method is particularly useful for computing a subset of eigenvalues, and their eigen- or Schur vectors, closest to a given shift. The proposed method is based on block iterations and can take advantage of a preconditioner if it is available. It does not need to perform exact shift-and-invert transformation. Standard and generalized eigenproblems are handled in a unified framework. Our numerical experiments demonstrate that GPLHR is generally more robust and efficient than existing methods, especially if the available memory is limited.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. M. Aktulga, A. Buluç, S. Williams, and C. Yang, {\it Optimizing sparse matrix-multiple vectors multiplication for nuclear configuration interaction calculations}, in Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2014), 2014.
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., {\it Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide}, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[3] E. Balslev and J. M. Combes, {\it Spectral properties of many-body Schrödinger operators with dilatation-analytic interactions}, Comm. Math. Phys., 22 (1971), pp. 280-294. · Zbl 0219.47005
[4] M. Benzi, G. H. Golub, and J. Liesen, {\it Numerical solution of saddle point problems}, Acta Numer., 14 (2005), pp. 1-137. · Zbl 1115.65034
[5] K. A. Cliffe, A. Spence, and S. J. Tavener, {\it The numerical analysis of bifurcation problems with application to fluid mechanics}, Acta Numer., 9 (2000), pp. 39-131. · Zbl 1005.65138
[6] H. C. Elman, A. Ramage, and D. J. Silvester, {\it IFISS: A Matlab toolbox for modelling incompressible flow}, ACM Trans. Math. Software, 33 (2007), 14. · Zbl 1365.65326
[7] H. C. Elman, D. J. Silvester, and A. J. Wathen, {\it Finite Elements and Fast Iterative Solvers}, 2nd ed., Oxford University Press, New York, 2014. · Zbl 1304.76002
[8] D. R. Fokkema, G. L. 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
[9] M. A. Freitag and A. Spence, {\it Shift-invert Arnoldi’s method with preconditioned iterative solves}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 942-969. · Zbl 1204.65034
[10] G. H. Golub and Q. Ye, {\it An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems}, SIAM J. Sci. Comput., 24 (2002), pp. 312-334. · Zbl 1016.65017
[11] A. Greenbaum, {\it Iterative Methods for Solving Linear Systems}, SIAM, Philadelphia, 1997. · Zbl 0883.65022
[12] M. H. Gutknecht, {\it Block Krylov space methods for linear systems with multiple right-hand sides: An introduction}, in Modern Mathematical Models, Methods and Algorithms for Real World Systems, I. S. Duff, A. H. Siddiqi, and O. Christensen, eds., Anamaya, New Delhi, 2007, pp. 420-447.
[13] M. Head-Gordon and T. J. Lee, {\it Single reference coupled cluster and perturbation theories of electronic excitation energies}, in Recent Advances in Coupled Cluster Methods, R. J. Bartlett, ed., World Scientific, Singapore, 1997, pp. 221-253.
[14] T. Helgaker, P. Jorgensen, and J. Olsen, {\it Molecular Electronic-Structure Theory}, Wiley, Chichester, 2000.
[15] Y. K. Ho, {\it The method of complex coordinate rotation and its applications to atomic collision processes}, Phys. Rep., 99 (1983), pp. 1-68.
[16] M. E. Hochstenbach and G. L. G. Sleijpen, {\it Harmonic and refined Rayleigh-Ritz for the polynomial eigenvalue problem}, Numer. Linear Algebra Appl., 15 (2008), pp. 35-54. · Zbl 1212.65150
[17] I. Kamwa, D. Lefebvre, and L. Loud, {\it Small signal analysis of hydro-turbine governors in large interconnected power plants}, IEEE Power Engineering Society Winter Meeting, Vol. 2, 2002, pp. 1178-1183.
[18] W. Kerner, {\it Computing the complex eigenvalue spectrum for resistive magnetohydrodynamics}, in Large Scale Eigenvalue Problems, J. Cullum and R. A. Willoughby, eds., Elsevier, Amsterdam, 1986, pp. 241-265.
[19] A. 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
[20] 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
[21] J. S. Langer, {\it Instabilities and pattern formation in crystal growth}, Rev. Modern Phys., 52 (1980), pp. 1-28.
[22] J. S. Langer and H. Muller-Krumbhaar, {\it Theory of dendritic growth-i. Elements of a stability analysis}, Acta Metallurgica, 26 (1978), pp. 1681-1687.
[23] R. B. Lehoucq, D. C. Sorensen, and C. Yang, {\it ARPACK User’s Guide: Solution of Large-Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods}, Software Environ. Tools 6, SIAM, Philadelphia, 1998. · Zbl 0901.65021
[24] 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
[25] R. Morgan, {\it On restarting the Arnoldi method for large nonsymmetric eigenvalue problems}, Math. Comp., 65 (1996), pp. 1213-1230. · Zbl 0857.65041
[26] R. B. Morgan, {\it Computing interior eigenvalues of large matrices}, Linear Algebra Appl., 154/156 (1991), pp. 289-309. · Zbl 0734.65029
[27] R. B. Morgan, {\it Generalizations of Davidson’s method for computing eigenvalues of large nonsymmetric matrices}, J. Comput. Phys., 101 (1992), pp. 287-291. · Zbl 0757.65046
[28] R. B. Morgan and D. S. Scott, {\it Generalizations of Davidson’s method for computing eigenvalues of sparse symmetric matrices}, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 817-825. · Zbl 0602.65020
[29] R. B. Morgan and M. Zeng, {\it Harmonic projection methods for large non-symmetric eigenvalue problems}, Numer. Linear Algebra Appl., 5 (1998), pp. 33-55. · Zbl 0937.65045
[30] B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[31] B. Philippe and Y. Saad, {\it On correction equations and domain decomposition for computing invariant subspaces}, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1471-1483. · Zbl 1173.65320
[32] G. Quillen and Q. Ye, {\it A block inverse-free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems}, J. Comput. Appl. Math., 233 (2010), pp. 1298-1313. · Zbl 1186.65044
[33] W. P. Reinhardt, {\it Complex coordinates in the theory of atomic and molecular structure and dynamics}, Annu. Rev. Phys. Chem., 33 (1982), pp. 223-255.
[34] M. Robbé, M. Sadkane, and A. Spence, {\it Inexact inverse subspace iteration with preconditioning applied to non-Hermitian eigenvalue problems}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 92-113. · Zbl 1269.65036
[35] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelpha, 2003. · Zbl 1031.65046
[36] Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, revised ed., Classics Appl. Math. 66, SIAM, Philadelphia, 2011. · Zbl 1242.65068
[37] Y. Saad and M. H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Statist. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018
[38] M. Sadkane, {\it Block-Arnoldi and Davidson methods for unsymmetric large eigenvalue problems}, Numer. Math., 64 (1993), pp. 195-211. · Zbl 0791.65021
[39] V. Simoncini, {\it Computational methods for linear matrix equations}, SIAM Rev., to appear. · Zbl 1386.65124
[40] G. L. G. Sleijpen and H. A. van der Vorst, {\it A Jacobi-Davidson iteration method for linear eigenvalue problems}, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 401-425. · Zbl 0860.65023
[41] P. Sonneveld and M. B. van Gijzen, {\it IDR(s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations}, SIAM J. Sci. Comput., 31 (2008), pp. 1035-1062. · Zbl 1190.65053
[42] A. Stathopoulos, Y. Saad, and K. Wu, {\it Dynamic thick restarting of the Davidson, and the implicitly restarted Arnoldi methods}, SIAM J. Sci. Comput., 19 (1998), pp. 227-245. · Zbl 0924.65028
[43] G. W. Stewart, {\it On the sensitivity of the eigenvalue problem \({A}x = λ {B}x\)}, SIAM J. Numer. Anal., 9 (1972), pp. 669-686. · Zbl 0252.65026
[44] G. W. Stewart and J.-G. Sun, {\it Matrix Perturbation Theory}, Academic Press, Boston, MA, 1990. · Zbl 0706.65013
[45] L. N. Trefethen and M. Embree, {\it Spectra and Pseudospectra}, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[46] E. Vecharynski and A. Knyazev, {\it Preconditioned locally harmonic residual method for computing interior eigenpairs of certain classes of Hermitian matrices}, SIAM J. Sci. Comput., 37 (2015), pp. S3-S29. · Zbl 1325.65054
[47] 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
[48] F. Xue and H. C. Elman, {\it Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation}, Linear Algebra Appl., 435 (2011), pp. 601-622. · Zbl 1253.65059
[49] F. Xue and H. C. Elman, {\it Fast inexact implicitly restarted Arnoldi method for generalized eigenvalue problems with spectral transformation}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 433-459. · Zbl 1263.65041
[50] D. Zuev, E. Vecharynski, C. Yang, N. Orms, and A. I. Krylov, {\it New algorithms for iterative matrix-free eigensolvers in quantum chemistry}, J. Comput. Chem., 36 (2015), pp. 273-284.
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.