Convergence theory for preconditioned eigenvalue solvers in a nutshell
From MaRDI portal
Publication:2362287
DOI10.1007/S10208-015-9297-1zbMATH Open1370.65018DBLPjournals/focm/ArgentatiKNOZ17arXiv1412.5005OpenAlexW3101845474WikidataQ59695730 ScholiaQ59695730MaRDI QIDQ2362287FDOQ2362287
Authors: Merico E. Argentati, Andrew Knyazev, Klaus Neymeyr, Evgueni Ovtchinnikov, Ming Zhou 
Publication date: 7 July 2017
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
Abstract: Preconditioned iterative methods for numerical solution of large matrix eigenvalue problems are increasingly gaining importance in various application areas, ranging from material sciences to data mining. Some of them, e.g., those using multilevel preconditioning for elliptic differential operators or graph Laplacian eigenvalue problems, exhibit almost optimal complexity in practice, i.e., their computational costs to calculate a fixed number of eigenvalues and eigenvectors grow linearly with the matrix problem size. Theoretical justification of their optimality requires convergence rate bounds that do not deteriorate with the increase of the problem size. Such bounds were pioneered by E. D'yakonov over three decades ago, but to date only a handful have been derived, mostly for symmetric eigenvalue problems. Just a few of known bounds are sharp. One of them is proved in [doi:10.1016/S0024-3795(01)00461-X] for the simplest preconditioned eigensolver with a fixed step size. The original proof has been greatly simplified and shortened in [doi:10.1137/080727567] by using a gradient flow integration approach. In the present work, we give an even more succinct proof, using novel ideas based on Karush-Kuhn-Tucker theory and nonlinear programming.
Full work available at URL: https://arxiv.org/abs/1412.5005
Recommendations
- Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers
- A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems
- A geometric theory for preconditioned inverse iteration. I: Extrema of Rayleigh quotient
- On preconditioned eigensolvers and invert-Lanczos processes
- On the convergence rate of a preconditioned subspace eigensolver
rate of convergenceeigenvalueeigenvectorgradientpreconditioneriterative methodsymmetricRayleigh quotientKarush-Kuhn-Tucker theory
Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Preconditioners for iterative methods (65F08)
Cites Work
- Templates for the Solution of Algebraic Eigenvalue Problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. II. Interior eigenvalues
- Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method
- A projected preconditioned conjugate gradient algorithm for computing many extreme eigenpairs of a Hermitian matrix
- Sharp Convergence Estimates for the Preconditioned Steepest Descent Method for Hermitian Eigenvalue Problems
- A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems
- Convergence analysis of gradient iterations for the symmetric eigenvalue problem
- Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers
- An indefinite variant of LOBPCG for definite matrix pencils
- Title not available (Why is that?)
- A Geometric Convergence Theory for the Preconditioned Steepest Descent Iteration
- Preconditioning eigensolvers -- an Oxymoron?
- Title not available (Why is that?)
- Low-rank tensor methods with subspace correction for symmetric eigenvalue problems
- Graph partitioning using matrix values for preconditioning symmetric positive definite systems
- Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues
Cited In (11)
- A mixed precision LOBPCG algorithm
- On the convergence rate of a preconditioned subspace eigensolver
- Sharp Ritz value estimates for restarted Krylov subspace iterations
- Hybrid eigensolvers for nuclear configuration interaction calculations
- Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers
- Preconditioning and convergence in the right norm
- Convergence characteristics of preconditioned Euler equations
- On the eigenvalue distribution of a class of preconditioning methods
- Sharp Convergence Estimates for the Preconditioned Steepest Descent Method for Hermitian Eigenvalue Problems
- Convergence theory of exact interpolation scheme for computing several eigenvectors
- Cluster robust estimates for block gradient-type eigensolvers
Uses Software
This page was built for publication: Convergence theory for preconditioned eigenvalue solvers in a nutshell
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362287)
