Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues

Szyld, Daniel; Xue, Fei

doi:10.1090/mcom/3083

Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues
HTML articles powered by AMS MathViewer

by Daniel B. Szyld and Fei Xue PDF

Math. Comp. 85 (2016), 2887-2918 Request permission

Abstract:

Efficient computation of extreme eigenvalues of large-scale linear Hermitian eigenproblems can be achieved by preconditioned conjugate gradient (PCG) methods. In this paper, we study PCG methods for computing extreme eigenvalues of nonlinear Hermitian eigenproblems of the form $T(\lambda )v=0$ that admit a nonlinear variational principle. We investigate some theoretical properties of a basic CG method, including its global and asymptotic convergence. We propose several variants of single-vector and block PCG methods with deflation for computing multiple eigenvalues, and compare them in arithmetic and memory cost. Variable indefinite preconditioning is shown to be effective to accelerate convergence when some desired eigenvalues are not close to the lowest or highest eigenvalue. The efficiency of variants of PCG is illustrated by numerical experiments. Overall, the locally optimal block preconditioned conjugate gradient (LOBPCG) is the most efficient method, as in the linear setting.

References

Maha Al-Ammari and Françoise Tisseur, Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification, Linear Algebra Appl. 436 (2012), no. 10, 3954–3973. MR 2914557, DOI 10.1016/j.laa.2010.08.035
P. Arbenz, Lecture Notes on Solving Large Scale Eigenvalue Problems, ETH Zürich, 2012.
P. Arbenz, U. L. Hetmaniuk, R. B. Lehoucq and R. S. Tuminaro, A comparison of eigensolvers for large-scale 3D modal analysis using AMG-preconditioned iterative methods, International Journal for Numerical Methods in Engineering, Vol. 64 (2005), pp. 204–236.
Timo Betcke and Daniel Kressner, Perturbation, extraction and refinement of invariant pairs for matrix polynomials, Linear Algebra Appl. 435 (2011), no. 3, 514–536. MR 2794589, DOI 10.1016/j.laa.2010.06.029
Timo Betcke, Nicholas J. Higham, Volker Mehrmann, Christian Schröder, and Françoise Tisseur, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software 39 (2013), no. 2, Art. 7, 28. MR 3031626, DOI 10.1145/2427023.2427024
T. Betcke and H. Voss, A Jacobi-Davidson type projection method for NEPs, Future Generation Computer Systems, Vol. 20 (2004), pp. 363–372.
M. M. Betcke and H. Voss, Restarting iterative projection methods for Hermitian nonlinear eigenvalue problems with minmax property, Report 157, Institute of Mathematics, Hamburg University of Technology, October, 2011.
Yunfeng Cai, Zhaojun Bai, John E. Pask, and N. Sukumar, Hybrid preconditioning for iterative diagonalization of ill-conditioned generalized eigenvalue problems in electronic structure calculations, J. Comput. Phys. 255 (2013), 16–30. MR 3109776, DOI 10.1016/j.jcp.2013.07.020
F. Chaitin-Chatelin and M. B. van Gijzen, Analysis of parameterized quadratic eigenvalue problems in computational acoustics with homotopic deviation theory, Numer. Linear Algebra Appl. 13 (2006), no. 6, 487–512. MR 2247445, DOI 10.1002/nla.484
C. Conca, J. Planchard, and M. Vanninathan, Fluids and periodic structures, RAM: Research in Applied Mathematics, vol. 38, John Wiley & Sons, Ltd., Chichester; Masson, Paris, 1995. MR 1652238
Y.H. Dai, Nonlinear Conjugate Gradient Methods, Wiley Encyclopedia of Operations Research and Management Science (2011), DOI:10.1002/9780470400531.eorms0183.
Alan Edelman, Tomás A. Arias, and Steven T. Smith, The geometry of algorithms with orthogonality constraints, SIAM J. Matrix Anal. Appl. 20 (1999), no. 2, 303–353. MR 1646856, DOI 10.1137/S0895479895290954
C. Effenberger, Robust successive computation of eigenpairs for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 1231–1256. MR 3092750, DOI 10.1137/120885644
Howard C. Elman, David J. Silvester, and Andrew J. Wathen, Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, 2nd ed., Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford, 2014. MR 3235759, DOI 10.1093/acprof:oso/9780199678792.001.0001
Giuseppe Gambolati, Flavio Sartoretto, and Paolo Florian, An orthogonal accelerated deflation technique for large symmetric eigenproblems, Comput. Methods Appl. Mech. Engrg. 94 (1992), no. 1, 13–23. MR 1148708, DOI 10.1016/0045-7825(92)90154-C
Nick Gould, Dominique Orban, and Philippe Toint, Numerical methods for large-scale nonlinear optimization, Acta Numer. 14 (2005), 299–361. MR 2168345, DOI 10.1017/S0962492904000248
Chun-Hua Guo, Nicholas J. Higham, and Françoise Tisseur, Detecting and solving hyperbolic quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1593–1613. MR 2486855, DOI 10.1137/070704058
K. P. Hadeler, Variationsprinzipien bei nichtlinearen Eigenwertaufgaben, Arch. Rational Mech. Anal. 30 (1968), 297–307 (German). MR 234322, DOI 10.1007/BF00281537
William W. Hager and Hongchao Zhang, A survey of nonlinear conjugate gradient methods, Pac. J. Optim. 2 (2006), no. 1, 35–58. MR 2548208
E. Jarlebring, The Spectrum of Delay-Differential Equations: Numerical Methods, Stability and Perturbation, PhD thesis, Inst. Comp. Math, TU Braunschweig, 2008.
A. V. Knyazev, A preconditioned conjugate gradient method for eigenvalue problems and its implementation in a subspace, Numerical treatment of eigenvalue problems, Vol. 5 (Oberwolfach, 1990) Internat. Ser. Numer. Math., vol. 96, Birkhäuser, Basel, 1991, pp. 143–154. MR 1109101, DOI 10.1007/978-3-0348-6332-2_{1}1
Andrew V. Knyazev, Preconditioned eigensolvers—an oxymoron?, Electron. Trans. Numer. Anal. 7 (1998), 104–123. Large scale eigenvalue problems (Argonne, IL, 1997). MR 1667642
Andrew V. Knyazev, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput. 23 (2001), no. 2, 517–541. Copper Mountain Conference (2000). MR 1861263, DOI 10.1137/S1064827500366124
Jorge Nocedal and Stephen J. Wright, Numerical optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940
Yousef Saad, Iterative methods for sparse linear systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645, DOI 10.1137/1.9780898718003
K. Schreiber, Nonlinear Eigenvalue Problems: Newton-type Methods and Nonlinear Rayleigh Functionals, Ph.D thesis, Department of Mathematics, TU Berlin, 2008.
Hubert Schwetlick and Kathrin Schreiber, Nonlinear Rayleigh functionals, Linear Algebra Appl. 436 (2012), no. 10, 3991–4016. MR 2914559, DOI 10.1016/j.laa.2010.06.048
Gerard L. G. Sleijpen and Henk A. Van der Vorst, A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 2, 401–425. MR 1384515, DOI 10.1137/S0895479894270427
Gerard L. G. Sleijpen, Albert G. L. Booten, Diederik R. Fokkema, and Henk A. Van der Vorst, Jacobi-Davidson type methods for generalized eigenproblems and polynomial eigenproblems, BIT 36 (1996), no. 3, 595–633. International Linear Algebra Year (Toulouse, 1995). MR 1410100, DOI 10.1007/BF01731936
Sergey I. Solov′ëv, Preconditioned iterative methods for a class of nonlinear eigenvalue problems, Linear Algebra Appl. 415 (2006), no. 1, 210–229. MR 2214753, DOI 10.1016/j.laa.2005.03.034
Daniel B. Szyld and Fei Xue, Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems, Numer. Math. 123 (2013), no. 2, 333–362. MR 3010183, DOI 10.1007/s00211-012-0489-1
Daniel B. Szyld, Eugene Vecharynski, and Fei Xue, Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. II. Interior eigenvalues, SIAM J. Sci. Comput. 37 (2015), no. 6, A2969–A2997. MR 3435092, DOI 10.1137/15M1016096
Heinrich Voss, A minmax principle for nonlinear eigenproblems depending continuously on the eigenparameter, Numer. Linear Algebra Appl. 16 (2009), no. 11-12, 899–913. MR 2567141, DOI 10.1002/nla.670
H. Voss, Nonlinear Eigenvalue Problems, Chapter 60 in L. Hogben (ed.), Handbook of Linear Algebra, CRC Press, Boca Raton 2014.
H. Voss and B. Werner, A minimax principle for nonlinear eigenvalue problems with applications to nonoverdamped systems, Math. Methods Appl. Sci. 4 (1982), no. 3, 415–424. MR 669135, DOI 10.1002/mma.1670040126
S. Wei and I. Kao, Vibration analysis of wire and frequency response in the modern wiresaw manufacturing process, Journal of Sound and Vibration, Vol. 231 (2000), pp. 1383–1395.
H. Yang, Conjugate gradient methods for the Rayleigh quotient minimization of generalized eigenvalue problems, Computing 51 (1993), no. 1, 79–94 (English, with English and German summaries). MR 1242660, DOI 10.1007/BF02243830