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
Additional Information
- Daniel B. Szyld
- Affiliation: Department of Mathematics, Temple University (038-16), 1805 N. Broad Street, Philadelphia, Pennsylvania 19122-6094
- MR Author ID: 244424
- Email: szyld@temple.edu
- Fei Xue
- Affiliation: Department of Mathematics, University of Louisiana at Lafayette, P.O. Box 41010, Lafayette, Louisiana 70504-1010
- MR Author ID: 880232
- Email: fxue@louisiana.edu
- Received by editor(s): August 27, 2014
- Received by editor(s) in revised form: April 28, 2015, and June 9, 2015
- Published electronically: February 19, 2016
- Additional Notes: The first author was supported by NSF under grants DMS-1115520 and DMS-1418882.
The second author was supported by NSF under grants DMS-1115520 and DMS-1419100. - © Copyright 2016 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 2887-2918
- MSC (2010): Primary 65F15, 65F50, 15A18, 15A22
- DOI: https://doi.org/10.1090/mcom/3083
- MathSciNet review: 3522974