×

Preconditioned gradient iterations for the eigenproblem of definite matrix pairs. (English) Zbl 1431.65046

Summary: Preconditioned gradient iterations for large and sparse Hermitian generalized eigenvalue problems \(Ax=\lambda Bx\), with positive definite \(B\), are efficient methods for computing a few extremal eigenpairs. In this paper we give a unifying framework of preconditioned gradient iterations for definite generalized eigenvalue problems with indefinite \(B\). More precisely, these iterations compute a few eigenvalues closest to the definiteness interval, which can be in the middle of the spectrum, and the corresponding eigenvectors of definite matrix pairs \((A,B)\), that is, pairs having a positive definite linear combination. Sharp convergence theorems for the simplest variants are given. This framework includes an indefinite locally optimal block preconditioned conjugate gradient (LOBPCG) algorithm derived by D. Kressner et al. [Numer. Algorithms 66, No. 4, 681–703 (2014; Zbl 1297.65040)]. We also give a generic algorithm for constructing new “indefinite extensions” of standard (with positive definite \(B)\) eigensolvers. Numerical experiments demonstrate the use of our algorithm for solving a product and a hyperbolic quadratic eigenvalue problem. With excellent preconditioners, the indefinite variant of LOBPCG is the most efficient method. Finally, we derive some ideas on how to use our indefinite eigensolver to compute a few eigenvalues around any spectral gap and the corresponding eigenvectors of definite matrix pairs.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F08 Preconditioners for iterative methods
65F50 Computational methods for sparse matrices

Citations:

Zbl 1297.65040
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] C. ASHCRAFT, R. G. GRIMES,ANDJ. G. LEWIS, Accurate symmetric indefinite linear equation solvers, SIAM J. Matrix Anal. Appl., 20 (1999), pp. 513-561. · Zbl 0923.65010
[2] Z. BAI, J. DEMMEL, J. DONGARRA, A. RUHE,ANDH.VAN DERVORST, eds., Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000. · Zbl 0965.65058
[3] Z. BAI ANDR.-C. LI, Minimization principles for the linear response eigenvalue problem I: Theory, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1075-1100. · Zbl 1263.65078
[4] , Minimization principles for the linear response eigenvalue problem II: Computation, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 392-416. · Zbl 1311.65102
[5] , Minimization principles and computation for the generalized linear response eigenvalue problem, BIT, 54 (2014), pp. 31-54. · Zbl 1293.65053
[6] Z. BAI, R. LI,ANDW. LIN, Linear response eigenvalue problem solved by extended locally optimal preconditioned conjugate gradient methods, Sci. China Math., 59 (2016), pp. 1443-1460. · Zbl 1358.65021
[7] P. BENNER ANDX. LIANG, Convergence analysis of extended LOBPCG for the extreme eigenvalue, in preparation.
[8] T. BETCKE, N. J. HIGHAM, V. MEHRMANN, C. SCHRÖDER,ANDF. TISSEUR, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software, 39 (2013), Art. 7 (28 pages). https://github.com/ftisseur/nlevp · Zbl 1295.65140
[9] R. BOISVERT, R. POZO, K. REMINGTON, B. MILLER,ANDR. LIPMAN, Matrix Market, National Institute of Standards and Technology, 1996. Available athttp://math.nist.gov/MatrixMarket/
[10] J. R. BUNCH, Analysis of the diagonal pivoting method, SIAM J. Numer. Anal., 8 (1971), pp. 656-680. · Zbl 0199.49801
[11] , Partial pivoting strategies for symmetric matrices, SIAM J. Numer. Anal., 11 (1974), pp. 521-528. · Zbl 0253.65024
[12] J. R. BUNCH ANDL. KAUFMAN, Some stable methods for calculating inertia and solving symmetric linear systems, Math. Comp., 31 (1977), pp. 163-179. · Zbl 0355.65023
[13] J. R. BUNCH, L. KAUFMAN,ANDB. N. PARLETT, Decomposition of a symmetric matrix, Numer. Math., 27 (1976), pp. 95-109. · Zbl 0342.65026
[14] J. R. BUNCH ANDR. F. MARCIA, A simplified pivoting strategy for symmetric tridiagonal matrices, Numer. Linear Algebra Appl., 13 (2006), pp. 865-867. · Zbl 1174.65348
[15] J. R. BUNCH ANDB. N. PARLETT, Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8 (1971), pp. 639-655. · Zbl 0199.49802
[16] J. W. DEMMEL, Applied Numerical Linear Algebra, SIAM, Philadelphia, 1997. · Zbl 0879.65017
[17] J. A. DUERSCH, M. SHAO, C. YANG,ANDM. GU, A robust and efficient implementation of LOBPCG, SIAM J. Sci. Comput., 40 (2018), pp. C655-C676. · Zbl 1401.65038
[18] I. DUFF, R. G. GRIMES,ANDJ. G. LEWIS, Users’ guide for the Harwell-Boeing sparse matrix collection, Technical report TR/PA/92/86, CERFACS, 1992.
[19] E. G. D’YAKONOV, Optimization in Solving Elliptic Problems, CRC Press, Boca Raton, 1996. ETNA · Zbl 0852.65087
[20] E. G. D’YAKONOV ANDM. Y. OREKHOV, Minimization of the computational labor in determining the first eigenvalues of differential operators, Math. Notes, 27 (1980), pp. 795-812. · Zbl 0468.65056
[21] G. H. GOLUB ANDQ. YE, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 24 (2002), pp. 312-334. · Zbl 1016.65017
[22] R. G. GRIMES, J. G. LEWIS,ANDH. D. SIMON, A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 228-272. · Zbl 0803.65044
[23] C.-H. GUO, N. J. HIGHAM,ANDF. TISSEUR, An improved arc algorithm for detecting definite Hermitian pairs, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 1131-1151. · Zbl 1202.65054
[24] V. HARI, S. SINGER,ANDS. SINGER, Block-oriented J -Jacobi methods for Hermitian matrices, Linear Algebra Appl., 433 (2010), pp. 1491-1512. · Zbl 1205.65152
[25] U. HETMANIUK ANDR. LEHOUCQ, Basis selection in LOBPCG, J. Comput. Phys., 218 (2006), pp. 324-332. · Zbl 1104.65031
[26] N. J. HIGHAM, F. TISSEUR,ANDP. M. VANDOOREN, Detecting a definite Hermitian pair and a hyperbolic or elliptic quadratic eigenvalue problem, and associated nearness problems, Linear Algebra Appl., 351/352 (2002), pp. 455-474. · Zbl 1004.65045
[27] HSL, HSL: A collection of Fortran codes for large scale scientific computation, 2011. http://www.hsl.rl.ac.uk.
[28] L. KAUFMAN, The retraction algorithm for factoring banded symmetric matrices, Numer. Linear Algebra Appl., 14 (2007), pp. 237-254. · Zbl 1199.65083
[29] A. V. KNYAZEV, Computation of Eigenvalues and Eigenvectors for Mesh Problems: Algorithms and Error Estimates, Dept. Numer. Math, USSR Acad. Sci., Moscow, 1986.
[30] , Convergence rate estimates for iterative methods for a mesh symmetric eigenvalue problem, Soviet J. Numer. Anal. Math. Modelling, 2 (1987), pp. 371-396. · Zbl 0825.65034
[31] , A preconditioned conjugate gradient method for eigenvalue problems and its implementation in a subspace, in Numerical Treatment of Eigenvalue Problems. Vol. 5., J. Albrecht, L. Collatz, P. Hagedorn and W. Velte, eds., vol. 96 of Internat. Ser. Numer. Math., Birkhäuser, Basel, 1991, pp. 143-154. · Zbl 0725.65042
[32] , Preconditioned eigensolvers—an oxymoron?, Electron. Trans. Numer. Anal., 7 (1998), pp. 104-123. http://etna.ricam.oeaw.ac.at/vol.7.1998/pp104-123.dir/pp104-123.pdf · Zbl 1053.65513
[33] , Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541. · Zbl 0992.65028
[34] A. V. KNYAZEV, M. E. ARGENTATI, I. LASHUK,ANDE. E. OVTCHINNIKOV, Block locally optimal preconditioned eigenvalue xolvers (BLOPEX) in hypre and PETSc, SIAM J. Sci. Comput., 29 (2007), pp. 2224-2239. · Zbl 1149.65026
[35] A. V. KNYAZEV ANDK. NEYMEYR, Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method, Electron. Trans. Numer. Anal., · Zbl 1031.65126
[36] , Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 621-628. · Zbl 1191.49039
[37] J. KOVA ˇC-STRIKO ANDK. VESELI ´C, Trace minimization and definiteness of symmetric pencils, Linear Algebra Appl., 216 (1995), pp. 139-158. · Zbl 0821.15008
[38] D. KRESSNER, M. MILOLOŽAPANDUR,ANDM. SHAO, An indefinite variant of LOBPCG for definite matrix pencils, Numer. Algorithms, 66 (2014), pp. 681-703. · Zbl 1297.65040
[39] P. LANCASTER ANDL. RODMAN, Canonical forms for Hermitian matrix pairs under strict equivalence and congruence, SIAM Rev., 47 (2005), pp. 407-443. · Zbl 1087.15014
[40] P. LANCASTER ANDQ. YE, Variational and numerical methods for symmetric matrix pencils, Bull. Austral. Math. Soc., 43 (1991), pp. 1-17. · Zbl 0714.65042
[41] X. LIANG ANDR.-C. LI, The hyperbolic quadratic eigenvalue problem, Forum Math. Sigma, 3 (2015), pp. e13, 93. · Zbl 1328.15033
[42] X. LIANG, R.-C. LI,ANDZ. BAI, Trace minimization principles for positive semi-definite pencils, Linear Algebra Appl., 438 (2013), pp. 3085-3106. · Zbl 1262.15010
[43] M. MILOLOŽAPANDUR, Computing Interior Eigenvalues and Corresponding Eigenvectors of Definite Matrix Pairs, PhD. Thesis, Faculty of Science, Department of Mathematics, University of Zagreb, 2016.
[44] K. NEYMEYR, A Hierarchy of Preconditioned Eigensolvers for Elliptic Differential Operators, Hab. Thesis, Mathematisches Institut, Universität Tübingen, 2001. · Zbl 0976.65034
[45] , On preconditioned eigensolvers and invert-Lanczos processes, Linear Algebra Appl., 430 (2009), pp. 1039-1056. · Zbl 1165.65071
[46] , A geometric convergence theory for the preconditioned steepest descent iteration, SIAM J. Numer. Anal., 50 (2012), pp. 3188-3207. · Zbl 1262.65051
[47] K. NEYMEYR, E. OVTCHINNIKOV,ANDM. ZHOU, Convergence analysis of gradient iterations for the symmetric eigenvalue problem, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 443-456. · Zbl 1230.65049
[48] K. NEYMEYR ANDM. ZHOU, The block preconditioned steepest descent iteration for elliptic operator eigenvalue problems, Electron. Trans. Numer. Anal., 41 (2014), pp. 93-108. http://etna.ricam.oeaw.ac.at/vol.41.2014/pp93-108.dir/pp93-108.pdf · Zbl 1295.65110
[49] B. N. PARLETT, The Symmetric Eigenvalue Problem, SIAM, Philadelphia, 1998. · Zbl 0885.65039
[50] B. T. POLYAK, Introduction to Optimization, Optimization Software, Inc., New York, 1987. · Zbl 0708.90083
[51] P. D. QUILLEN, Generalizations of an Inverse Free Krylov Subspace Method for the Symmetric Generalized Eigenvalue Problem, PhD. Thesis, Department of Mathematics, University of Kentucky, Lexington, 2005.
[52] P. QUILLEN ANDQ. YE, 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
[53] D. ROCCA, Z. BAI, R.-C. LI,ANDG. GALLI, A block variational procedure for the iterative diagonalization of non-Hermitian random-phase approximation matrices, J. Chem. Phys., 136 (2012), Art. 034111 (8 pages).
[54] I. SLAPNI ˇCAR, Componentwise analysis of direct factorization of real symmetric and Hermitian matrices, Linear Algebra Appl., 272 (1998), pp. 227-275. · Zbl 0894.65009
[55] G. W. STEWART ANDJ. G. SUN, Matrix Perturbation Theory, Academic Press, Boston, 1990. · Zbl 0706.65013
[56] D. B. SZYLD ANDF. XUE, Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues, Math. Comp., 85 (2016), pp. 2887-2918. · Zbl 1344.65045
[57] K. VESELI ´C, A Jacobi eigenreduction algorithm for definite matrix pairs, Numer. Math., 64 (1993), pp. 241- 269. · Zbl 0805.65038
[58] K. VESELI ´C, Damped Oscillations of Linear Systems. A Mathematical Introduction, Springer, Heidelberg, 2011. · Zbl 1232.37004
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.