Convergence theory for preconditioned eigenvalue solvers in a nutshell
From MaRDI portal
Publication:2362287
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.
Suppose \(Ax=\mu Bx\) has ordered eigenvalues \(\mu_i\). In this paper iterates of the form \(x'=x -\frac{1}{\mu(x)} T(A-\mu(x)I)Ax\) are considered with \(\mu(x)=x^TBx/x^TAx\) the Rayleigh quotient and \(T\) a preconditioner such that the maximal singular value of \(I-A^{1/2}TA^{1/2}\) is bounded by \(\gamma<1\). Sharp bounds for the rate of convergence are proved. It is essentially given by \(\sigma^2\) with \(\sigma=\gamma+(1-\gamma)\mu_{i+1}/\mu_i\) if \(\mu(x)\in(\mu_{i+1},\mu_i)\). Such results were proved before by two of the authors [\textit{A. V. Knyazev} and \textit{K. Neymeyr}, Linear Algebra Appl. 358, No. 1--3, 95--114 (2003; Zbl 1037.65039); SIAM J. Matrix Anal. Appl. 31, No. 2, 621--628 (2009; Zbl 1191.49039)]. Here the proofs are simplified based on nonlinear programming and Karush-Kuhn-Tucker (KKT) theory.
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
Cites work
- A Geometric Convergence Theory for the Preconditioned Steepest Descent Iteration
- A geometric theory for preconditioned inverse iteration. III: A short and sharp convergence estimate for generalized eigenvalue problems
- A projected preconditioned conjugate gradient algorithm for computing many extreme eigenpairs of a Hermitian matrix
- An indefinite variant of LOBPCG for definite matrix pencils
- Convergence analysis of gradient iterations for the symmetric eigenvalue problem
- Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method
- Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers
- Graph partitioning using matrix values for preconditioning symmetric positive definite systems
- scientific article; zbMATH DE number 1243473 (Why is no real title available?)
- scientific article; zbMATH DE number 766233 (Why is no real title available?)
- scientific article; zbMATH DE number 919117 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Low-rank tensor methods with subspace correction for symmetric eigenvalue problems
- Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. I. Extreme eigenvalues
- Preconditioned eigensolvers for large-scale nonlinear Hermitian eigenproblems with variational characterizations. II. Interior eigenvalues
- Preconditioning eigensolvers -- an Oxymoron?
- Sharp Convergence Estimates for the Preconditioned Steepest Descent Method for Hermitian Eigenvalue Problems
- Templates for the Solution of Algebraic Eigenvalue Problems
Cited in
(16)- On the eigenvalue distribution of a class of preconditioning methods
- Sharp Ritz value estimates for restarted Krylov subspace iterations
- On the convergence rate of a preconditioned subspace eigensolver
- Convergence characteristics of preconditioned Euler equations
- Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers
- Cluster robust estimates for block gradient-type eigensolvers
- Preconditioning and convergence in the right norm
- Sharp Convergence Estimates for the Preconditioned Steepest Descent Method for Hermitian Eigenvalue Problems
- Convergence theory of exact interpolation scheme for computing several eigenvectors
- Hybrid eigensolvers for nuclear configuration interaction calculations
- A mixed precision LOBPCG algorithm
- Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- Accelerating eigenvalue computation for nuclear structure calculations via perturbative corrections
- Riemannian acceleration with preconditioning for symmetric eigenvalue problems
- EPIC: a provable accelerated eigensolver based on preconditioning and implicit convexity
- On a shrink-and-expand technique for symmetric block eigensolvers
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)
