Preconditioned locally harmonic residual method for computing interior eigenpairs of certain classes of Hermitian matrices. (English) Zbl 1325.65054
Summary: We propose a preconditioned locally harmonic residual (PLHR) method for computing several interior eigenpairs of a generalized Hermitian eigenvalue problem, without traditional spectral transformations, matrix factorizations, or inversions. PLHR is based on a short-term recurrence, easily extended to a block form, computing eigenpairs simultaneously. PLHR can take advantage of Hermitian positive definite preconditioning, e.g., based on an approximate inverse of an absolute value of a shifted matrix, introduced in [the authors, ibid. 35, No. 2, A696-A718 (2013; Zbl 1266.15004)]. Our numerical experiments demonstrate that PLHR is efficient and robust for certain classes of large-scale interior eigenvalue problems, involving Laplacian and Hamiltonian operators, especially if memory requirements are tight.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F08 | Preconditioners for iterative methods |
| 65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |
| 15B57 | Hermitian, skew-Hermitian, and related matrices |
Citations:
Zbl 1266.15004References:
| [1] | O. Axelsson, {\it Iterative Solution Methods}, Cambridge University Press, New York, 1994. · Zbl 0795.65014 |
| [2] | Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, eds., {\it Templates for the Solution of Algebraic Eigenvalue Problems}, SIAM, Philadelphia, 2000. · Zbl 0965.65058 |
| [3] | A. Borzì and G. Borzì, {\it Algebraic multigrid methods for solving generalized eigenvalue problems}, Internat. J. Numer. Methods Engrg., 65 (2005), pp. 1186-1196. · Zbl 1114.65035 |
| [4] | W. L. Briggs, V. E. Henson, and S. F. McCormick, {\it A Multigrid Tutorial}, 2nd ed., SIAM, Philadelphia, 2000. · Zbl 0958.65128 |
| [5] | H. C. Elman, O. G. Ernst, and D. O’Leary, {\it A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations}, SIAM J. Sci. Comput., 23 (2001), pp. 1291-1315. · Zbl 1004.65134 |
| [6] | H. Fang and Y. Saad, {\it A filtered Lanczos procedure for extreme and interior eigenvalue problems}, SIAM J. Sci. Comput., 34 (2012), pp. A2220-A2246. · Zbl 1253.65053 |
| [7] | G. H. Golub and C. F. V. Loan, {\it Matrix Computations}, 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996. · Zbl 0865.65009 |
| [8] | 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 |
| [9] | A. Greenbaum, {\it Iterative Methods for Solving Linear Systems}, SIAM, Philadelphia, 1997. · Zbl 0883.65022 |
| [10] | U. Hetmaniuk, {\it A Rayleigh quotient minimization algorithm based on algebraic multigrid}, Numer. Linear Algebra Appl., 14 (2007), pp. 563-580. · Zbl 1199.65119 |
| [11] | Z. Jia, {\it Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems}, Linear Algebra Appl., 259 (1997), pp. 1-23. · Zbl 0877.65018 |
| [12] | G. Jordan, M. Marsman, Y.-S. Kim, and G. Kresse, {\it Fast iterative interior eigensolver for millions of atoms}, J. Comput. Phys., 231 (2012), pp. 4836-4847. · Zbl 1251.82061 |
| [13] | A. V. Knyazev, {\it Computation of Eigenvalues and Eigenvectors for Mesh Problems: Algorithms and error estimates}, Department of Numerical Mathematics USSR Academy of Sciences, Moscow, 1986 (in Russian). |
| [14] | 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 |
| [15] | A. V. Knyazev, {\it Preconditioned eigensolvers–an oxymoron?}, Electron. Trans. Numer. Anal., 7 (1998), pp. 104-123. · Zbl 1053.65513 |
| [16] | 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., 25 (2007), pp. 2224-2239. · Zbl 1149.65026 |
| [17] | W. Kohn and L. Sham, {\it Self-consistent equations including exchange and correlation effects}, Phys. Rev., 140 (1965), pp. A1133-A1138. |
| [18] | G. Kresse and J. Furthmüller, {\it Efficiency of ab-initio total energy calculations for metals and semiconductors using a plane-wave basis set}, Computational Materials Science, 6 (1996), pp. 15-50. |
| [19] | D. Kushnir, M. Galun, and A. Brandt, {\it Efficient multilevel eigensolvers with applications to data analysis tasks}, IEEE Trans. Pattern. Anal. Mach. Intell., 32 (2010), pp. 1377-1391. |
| [20] | I. Livshits, {\it An algebraic multigrid wave-ray algorithm to solve eigenvalue problems for the Helmholtz operator}, Numer. Linear Algebra Appl., 11 (2004), pp. 229-239. · Zbl 1164.65492 |
| [21] | I. Livshits and A. Brandt, {\it Accuracy properties of the wave-ray multigrid algorithm for Helmholtz equations}, SIAM J. Sci. Comput., 28 (2006), pp. 1228-1251. · Zbl 1119.65109 |
| [22] | R. B. Morgan, {\it Computing interior eigenvalues of large matrices}, Linear Algebra Appl., 154-156 (1991), pp. 289-309. · Zbl 0734.65029 |
| [23] | 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 |
| [24] | C. C. Paige, B. N. Parlett, and H. A. van der Vorst, {\it Approximate solutions and eigenvalue bounds from Krylov subspaces}, Numer. Linear Algebra Appl., 2 (1995), pp. 115-133. · Zbl 0831.65036 |
| [25] | C. C. Paige and M. A. Saunders, {\it Solution of sparse indefinite systems of linear equations}, SIAM J. Numer. Anal., 12 (1975), pp. 617-629. · Zbl 0319.65025 |
| [26] | B. N. Parlett, {\it The Symmetric Eigenvalue Problem}, Classics Appl. Math. 20, SIAM, Philadelphia, 1998. · Zbl 0885.65039 |
| [27] | Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, SIAM, Philadelpha, 2003. · Zbl 1031.65046 |
| [28] | Y. Saad, {\it Numerical Methods for Large Eigenvalue Problems}, SIAM, Philadelpha, 2011. · Zbl 1242.65068 |
| [29] | 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 |
| [30] | G. L. G. Sleijpen and H. A. V. 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 |
| [31] | G. W. Stewart, {\it Matrix Algorithms} Vol. II, SIAM, Philadelpha, 2001. · Zbl 0984.65031 |
| [32] | M. P. Teter, M. C. Payne, and D. C. Allan, {\it Solution of Schrödinger’s equation for large systems}, Phys. Rev. B, 40 (1989), pp. 12255-12263. |
| [33] | U. Trottenberg, C. W. Oosterlee, and A. Schüller, {\it Multigrid}, Academic Press, New York, 2001. · Zbl 0976.65106 |
| [34] | E. Vecharynski, {\it Preconditioned Iterative Methods for Linear Systems, Eigenvalue and Singular Value Problems}, Ph.D. thesis, University of Colorado, Denver, 2011. |
| [35] | E. Vecharynski and A. V. Knyazev, {\it Absolute value preconditioning for symmetric indefinite linear systems}, SIAM J. Sci. Comput., 35 (2013), pp. A696-A718. · Zbl 1266.15004 |
| [36] | C. Vömel, {\it A note on harmonic Ritz values and their reciprocals}, Numer. Linear Algebra Appl., 17 (2010), pp. 97-108. · Zbl 1240.65125 |
| [37] | L. W. Wang and J. Li, {\it First-principles thousand-atom quantum dot calculations}, Phys. Rev. B, 69 (2004), 153302. |
| [38] | L. W. Wang and A. Zunger, {\it Local-density-derived semiempirical pseudopotentials}, Phys. Rev. B, 51 (1995), pp. 17398-17416. |
| [39] | L. W. Wang and A. Zunger, {\it Linear combination of bulk bands method for large-scale electronic structure calculations on strained nanostructures}, Phys. Rev. B, 59 (1999), pp. 15806-15818. |
| [40] | D. Wood and A. Zunger, {\it A new method for diagonalising large matrices}, J. Phys. A Math. General, 18 (1985), p. 1343. · Zbl 0615.65043 |
| [41] | C. Yang, J. Meza, B. Lee, and L.-W. Wang, {\it KSSOLV–A MATLAB toolbox for solving the Kohn-Sham equations}, ACM Trans. Math. Software, 36 (2009), pp. 10:1-10:35. · Zbl 1364.65112 |
| [42] | D. M. Young and K. C. Jea, {\it Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods}, Linear Algebra Appl., 34 (1980), pp. 159-194. · Zbl 0463.65025 |
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.
