Volume 51, pp. 331-362, 2019.

Preconditioned gradient iterations for the eigenproblem of definite matrix pairs

Marija Miloloža Pandur

Abstract

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 Kressner, Miloloža Pandur, and Shao [Numer. Algorithms, 66 (2014), pp. 681–703]. 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.

Full Text (PDF) [611 KB], BibTeX , DOI: 10.1553/etna_vol51s331

Key words

eigenpair, definite matrix pair, definitizing shift, definiteness interval, spectral gap, preconditioned steepest descent/ascent iteration, indefinite LOBPCG

AMS subject classifications

65F15, 65F08, 65F50

Links to the cited ETNA articles

[32]	Vol. 7 (1998), pp. 104-123 Andrew V. Knyazev: Preconditioned eigensolvers - an oxymoron?
[35]	Vol. 15 (2003), pp. 38-55 Andrew V. Knyazev and Klaus Neymeyr: Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method
[48]	Vol. 41 (2014), pp. 93-108 Klaus Neymeyr and Ming Zhou: The block preconditioned steepest descent iteration for elliptic operator eigenvalue problems