Jacobi correction equation, line search and conjugate gradients in Hermitian eigenvalue computation I: computing an extreme eigenvalue

Ovtchinnikov, E. 2008. Jacobi correction equation, line search and conjugate gradients in Hermitian eigenvalue computation I: computing an extreme eigenvalue. SIAM Journal on Numerical Analysis. 46 (5), pp. 2567-2592.

TitleJacobi correction equation, line search and conjugate gradients in Hermitian eigenvalue computation I: computing an extreme eigenvalue
AuthorsOvtchinnikov, E.
Abstract

This paper is concerned with the convergence properties of iterative algorithms of conjugate gradient type applied to the computation of an extreme eigenvalue of a Hermitian operator via the optimization of the Rayleigh quotient functional. The algorithms in focus employ the line search for the extremum of the Rayleigh quotient functional in the direction that is a linear combination of the gradient and the previous search direction. An asymptotically explicit equation for the reduction in the eigenvalue error after the line search step as a function of the search direction is derived and applied to the analysis of the local convergence properties (i.e., the error reduction after an iteration) of the algorithms in question. The local (stepwise) asymptotic equivalence of various conjugate gradient algorithms and the generalized Davidson method is proved, and a new convergence estimate for conjugate gradient iterations is derived, showing the reduction in the eigenvalue error after any two consecutive iterations. The paper's analysis extensively employs remarkable properties of the operator of the so-called Jacobi orthogonal complement correction equation.

KeywordsHermitian eigenvalue computation, Jacobi orthogonal complement correction equation, conjugate gradients, convergence estimates, generalized Davidson method
JournalSIAM Journal on Numerical Analysis
Journal citation46 (5), pp. 2567-2592
ISSN0036-1429
YearMay 2008
PublisherSociety for Industrial and Applied Mathematics
Digital Object Identifier (DOI)doi:10.1137/070688742
Publication dates
PublishedMay 2008

Related outputs

Computing several eigenpairs of Hermitian problems by conjugate gradient iterations
Ovtchinnikov, E. 2008. Computing several eigenpairs of Hermitian problems by conjugate gradient iterations. Journal of Computational Physics. 227 (22), pp. 9477-9497.

Jacobi correction equation, line search, and conjugate gradients in Hermitian eigenvalue computation II: computing several extreme eigenvalues
Ovtchinnikov, E. 2008. Jacobi correction equation, line search, and conjugate gradients in Hermitian eigenvalue computation II: computing several extreme eigenvalues. SIAM Journal on Numerical Analysis. 46 (5), pp. 2593-2619.

Block locally optimal preconditioned eigenvalue Xolvers (BLOPEX) in Hypre and PETSc
Knyazev, A.V., Argentati, M.E., Lashuk, I. and Ovtchinnikov, E. 2007. Block locally optimal preconditioned eigenvalue Xolvers (BLOPEX) in Hypre and PETSc. SIAM Journal on Scientific Computing. 29 (5), pp. 2224-2239.

Cluster robustness of preconditioned gradient subspace iteration eigensolvers
Ovtchinnikov, E. 2006. Cluster robustness of preconditioned gradient subspace iteration eigensolvers. Linear Algebra and its Applications. 415 (1), pp. 140-166.

Cluster robust error estimates for the Rayleigh-Ritz approximation II: Estimates for eigenvalues
Ovtchinnikov, E. 2006. Cluster robust error estimates for the Rayleigh-Ritz approximation II: Estimates for eigenvalues. Linear Algebra and its Applications. 415 (1), pp. 188-209.

Cluster robust error estimates for the Rayleigh-Ritz approximation I: Estimates for invariant subspaces
Ovtchinnikov, E. 2006. Cluster robust error estimates for the Rayleigh-Ritz approximation I: Estimates for invariant subspaces. Linear Algebra and its Applications. 415 (1), pp. 167-187.

Sharp convergence estimates for the preconditioned steepest descent method for hermitian eigenvalue problems
Ovtchinnikov, E. 2006. Sharp convergence estimates for the preconditioned steepest descent method for hermitian eigenvalue problems. SIAM Journal on Numerical Analysis. 43 (6), pp. 2668-2689.

Convergence estimates for the generalized davidson method for symmetric eigenvalue problems II: the subspace acceleration
Ovtchinnikov, E. 2003. Convergence estimates for the generalized davidson method for symmetric eigenvalue problems II: the subspace acceleration. SIAM Journal on Numerical Analysis. 41 (1), pp. 272-286.

Convergence estimates for the generalized davidson method for symmetric eigenvalue problems I: the preconditioning aspect
Ovtchinnikov, E. 2003. Convergence estimates for the generalized davidson method for symmetric eigenvalue problems I: the preconditioning aspect. SIAM Journal on Numerical Analysis. 41 (1), pp. 258-271.

On the opodeictics of successive eigenvalue relaxation for large-scale eigenvalue problems: proofs of convergence estimates
Xanthis, L. and Ovtchinnikov, E. 2002. On the opodeictics of successive eigenvalue relaxation for large-scale eigenvalue problems: proofs of convergence estimates. HERMIS: the International Journal of Computer Mathematics and its Applications. 3, pp. 65-90.

Successive eigenvalue relaxation: a new method for the generalized eigenvalue problem and convergence estimates
Ovtchinnikov, E. and Xanthis, L. 2001. Successive eigenvalue relaxation: a new method for the generalized eigenvalue problem and convergence estimates. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 457 (2006), pp. 441-451.

Permalink - https://westminsterresearch.westminster.ac.uk/item/9129w/jacobi-correction-equation-line-search-and-conjugate-gradients-in-hermitian-eigenvalue-computation-i-computing-an-extreme-eigenvalue


Share this
Tweet
Email