Sharp a priori convergence estimates for Krylov subspace eigensolvers
Final Report Abstract
Linear systems and matrix eigenvalue problems can efficiently be solved by iterative methods in Krylov subspaces. The topicality of such methods is exemplified by applications to spectral clustering in data analysis or self-consistent field iterations in quantum mechanical density functional theory. The basic principle is the solution of a high-dimensional problem by means of a sequence of approximate solutions from adaptively improved subspaces of smaller dimensions. The simplicity of the method construction is contrasted with a high complexity of the description of its convergence behavior. This project is concerned with the convergence analysis of Krylov subspace methods for Hermitian eigenvalues problems with blockwise iterations, restarts and preconditioning. Therein the following results have been achieved. (i) Krylov subspace methods without preconditioning or with exact inverse preconditioning have been investigated by an advanced analysis via abstract blockwise iterations. Existing majorization approaches are extended by biorthogonal auxiliary vectors in order to describe approximation errors of iterative subspaces or Ritz values in terms of tuplewise convergence factors. The resulting estimates are applicable to various eigensolvers and filters. The specialization for block Krylov subspaces or the block Lanczos method improves existing results using scalar convergence factors. (ii) Some drawbacks of angle-dependent Ritz value estimates in the case of restarts have been overcome by angle-free variants. The derivation uses accompanying subspace iterations and recursively combines corresponding intermediate estimates. This enables inter alia multi-step estimates for restarted versions of the block Lanczos method. (iii) For preconditioned gradient iterations with implicit deflation some new estimates under weaker assumptions have been obtained and subsequently generalized to block versions. A modified interpretation of preconditioning for deflation is particularly important and can be reused in the future research of advanced methods with implicit deflation. (iv) Concerning the cluster robustness of blockwise preconditioned gradient iterations some approaches developed for fixed step sizes have been extended to optimal step sizes. This improves existing results in terms of flexible applicability and simple convergence factors.
Publications
-
Convergence analysis of a block preconditioned steepest descent eigensolver with implicit deflation. Numerical Linear Algebra with Applications, 30(5).
Zhou, Ming; Bai, Zhaojun; Cai, Yunfeng & Neymeyr, Klaus
-
Convergence rates of individual Ritz values in block preconditioned gradient-type eigensolvers. ETNA -Electronic Transactions on Numerical Analysis, 58, 597-620.
Zhou, Ming & Neymeyr, Klaus
-
Sharp Majorization-Type Cluster Robust Bounds for Block Filters and Eigensolvers. SIAM Journal on Matrix Analysis and Applications, 44(4), 1852-1878.
Zhou, Ming; Argentati, Merico; Knyazev, Andrew V. & Neymeyr, Klaus
-
Angle‐Free Cluster‐Robust Ritz Value Bounds for Restarted Block Eigensolvers. Numerical Linear Algebra with Applications, 32(1).
Zhou, Ming; Knyazev, Andrew & Neymeyr, Klaus
