Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Daniel B. Szyld and Fei Xue
Journal: Math. Comp. 85 (2016), 2887-2918
MSC (2010): Primary 65F15, 65F50, 15A18, 15A22
DOI: https://doi.org/10.1090/mcom/3083
Published electronically: February 19, 2016
MathSciNet review: 3522974
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Maha Al-Ammari and Francoise Tisseur, Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification, Linear Algebra Appl. 436 (2012), no. 10, 3954-3973. MR 2914557, https://doi.org/10.1016/j.laa.2010.08.035
  • [2] P. Arbenz, Lecture Notes on Solving Large Scale Eigenvalue Problems, ETH Zürich, 2012.
  • [3] 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.
  • [4] Timo Betcke and Daniel Kressner, Perturbation, extraction and refinement of invariant pairs for matrix polynomials, Linear Algebra Appl. 435 (2011), no. 3, 574-536. MR 2794589 (2012h:15012), https://doi.org/10.1016/j.laa.2010.06.029
  • [5] 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, https://doi.org/10.1145/2427023.2427024
  • [6] T. Betcke and H. Voss, A Jacobi-Davidson type projection method for NEPs, Future Generation Computer Systems, Vol. 20 (2004), pp. 363-372.
  • [7] 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.
  • [8] 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, https://doi.org/10.1016/j.jcp.2013.07.020
  • [9] 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 (2007c:65031), https://doi.org/10.1002/nla.484
  • [10] 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 (99k:73094)
  • [11] Y.H. Dai, Nonlinear Conjugate Gradient Methods, Wiley Encyclopedia of Operations Research and Management Science (2011), DOI:10.1002/9780470400531.eorms0183.
  • [12] 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 (99h:65075), https://doi.org/10.1137/S0895479895290954
  • [13] C. Effenberger, Robust successive computation of eigenpairs for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 1231-1256. MR 3092750, https://doi.org/10.1137/120885644
  • [14] 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
  • [15] 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 (92i:65072), https://doi.org/10.1016/0045-7825(92)90154-C
  • [16] Nick Gould, Dominique Orban, and Philippe Toint, Numerical methods for large-scale nonlinear optimization, Acta Numer. 14 (2005), 299-361. MR 2168345 (2006h:90068), https://doi.org/10.1017/S0962492904000248
  • [17] Chun-Hua Guo, Nicholas J. Higham, and Francoise Tisseur, Detecting and solving hyperbolic quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1593-1613. MR 2486855 (2010b:15021), https://doi.org/10.1137/070704058
  • [18] K. P. Hadeler, Variationsprinzipien bei nichtlinearen Eigenwertaufgaben, Arch. Rational Mech. Anal. 30 (1968), 297-307 (German). MR 0234322 (38 #2639)
  • [19] William W. Hager and Hongchao Zhang, A survey of nonlinear conjugate gradient methods, Pac. J. Optim. 2 (2006), no. 1, 35-58. MR 2548208 (2010h:90095)
  • [20] E. Jarlebring, The Spectrum of Delay-Differential Equations: Numerical Methods, Stability and Perturbation, PhD thesis, Inst. Comp. Math, TU Braunschweig, 2008.
  • [21] 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, https://doi.org/10.1007/978-3-0348-6332-2_11
  • [22] Andrew V. Knyazev, Preconditioned eigensolvers--an oxymoron?, Electron. Trans. Numer. Anal. 7 (1998), 104-123 (electronic). Large scale eigenvalue problems (Argonne, IL, 1997). MR 1667642 (99h:65068)
  • [23] 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 (electronic). Copper Mountain Conference (2000). MR 1861263 (2003g:65050), https://doi.org/10.1137/S1064827500366124
  • [24] Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer Series in Operations Research and Financial Engineering, Springer, New York, 2006. MR 2244940 (2007a:90001)
  • [25] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. MR 1990645 (2004h:65002)
  • [26] K. Schreiber, Nonlinear Eigenvalue Problems: Newton-type Methods and Nonlinear Rayleigh Functionals, Ph.D thesis, Department of Mathematics, TU Berlin, 2008.
  • [27] Hubert Schwetlick and Kathrin Schreiber, Nonlinear Rayleigh functionals, Linear Algebra Appl. 436 (2012), no. 10, 3991-4016. MR 2914559, https://doi.org/10.1016/j.laa.2010.06.048
  • [28] 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 (96m:65042), https://doi.org/10.1137/S0895479894270427
  • [29] 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 (97k:65095), https://doi.org/10.1007/BF01731936
  • [30] 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 (2007c:65036), https://doi.org/10.1016/j.laa.2005.03.034
  • [31] 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, https://doi.org/10.1007/s00211-012-0489-1
  • [32] 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, https://doi.org/10.1137/15M1016096
  • [33] 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 (2010k:49101), https://doi.org/10.1002/nla.670
  • [34] H. Voss, Nonlinear Eigenvalue Problems, Chapter 60 in L. Hogben (ed.), Handbook of Linear Algebra, CRC Press, Boca Raton 2014.
  • [35] 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 (84a:49063), https://doi.org/10.1002/mma.1670040126
  • [36] 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.
  • [37] 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 (94h:65040), https://doi.org/10.1007/BF02243830

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F15, 65F50, 15A18, 15A22

Retrieve articles in all journals with MSC (2010): 65F15, 65F50, 15A18, 15A22


Additional Information

Daniel B. Szyld
Affiliation: Department of Mathematics, Temple University (038-16), 1805 N. Broad Street, Philadelphia, Pennsylvania 19122-6094
Email: szyld@temple.edu

Fei Xue
Affiliation: Department of Mathematics, University of Louisiana at Lafayette, P.O. Box 41010, Lafayette, Louisiana 70504-1010
Email: fxue@louisiana.edu

DOI: https://doi.org/10.1090/mcom/3083
Keywords: Nonlinear Hermitian eigenproblems, variational principle, preconditioned conjugate gradient, convergence analysis
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.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society