Sharp a priori convergence estimates for Krylov subspace eigensolvers

椭圆型和自伴微分算子的特征值问题广泛存在于各种科学和技术应用中。它们的数值解是通过自适应有限元离散和迭代计算离散算子的期望特征对而获得的。众所周知，子空间迭代法是求解高维矩阵特征值问题的一种快速方法，并且比经典的对角化方法具有更高的效率。流行的子空间迭代适用于Krylov子空间，可以理解为已有近70年历史的Lanczos方法的改进变体。主要的程序变体包括重新启动、分块实现和预条件。相关的趋同理论已经不能跟上积极发展新的程序变体的步伐。此外，许多收敛估计具有后验性质，即它们通过复杂的公式来限制收敛速度，该公式取决于(将被计算的)Ritz值。该项目研究了实和对称矩阵特征值问题的Krylov子空间迭代的收敛分析的新方法。首先，分析了四种基本的迭代方法：标准Krylov子空间迭代、重新开始Krylov子空间迭代、块-Krylov子空间迭代和重新开始块-Krylov子空间迭代。由此得到的估计应该有助于更好地理解这些子空间迭代的收敛行为。计划对相关的预条件迭代进行扩展。其中一个重点是先验估计，它可以在相当弱的假设下推导出来，并具有不太复杂的界限。概率技术在推导实际收敛速度方面具有很高的潜力，并将与Rayleigh商水平集的几何解释和预条件相结合。对块数和块大小的新的自适应控制技术表明效率得到了提高，这一点应该在量子力学密度泛函理论中的自洽场迭代等应用问题上得到证明。

Eigenvalue problems of elliptic and self-adjoint differential operators occur in various scientific and technical applications. Their numerical solution succeeds by means of an adaptive finite element discretization and the iterative computation of the desired eigenpairs of the discretized operators. Subspace iterations are well known to be fast solution methods for the high-dimensional matrix eigenvalue problems and are considerably more efficient than classical diagonalization methods. Popular subspace iterations work in Krylov subspaces and can be understood as improved variants of the almost 70 years old Lanczos method. The main procedural variants include restarts, blockwise implementation and preconditioning. The associated convergence theory has not been able to keep pace with the active development of new procedural variants. In addition, many convergence estimates have an a posteriori character, i.e. they bound the rates of convergence by means of complicated formula that depend on the (to be) calculated Ritz values.The proposed project deals with new approaches for the convergence analysis of Krylov subspace iterations for real and symmetric matrix eigenvalue problems. First of all, four basic iteration methods are analyzed: standard Krylov subspace iterations, restarted Krylov subspace iterations, block-Krylov subspace iterations, and restarted block-Krylov subspace iterations. The resulting estimates should lead to an improved understanding of the convergence behavior of these subspace iterations. An extension to the related preconditioned iterations is planned. One focus is on a priori estimates, which can be derived under rather weak assumptions and work with less complex bounds. Probabilistic techniques have a high potential for deriving realistic convergence rates and will be combined with geometric interpretations of Rayleigh quotient level sets and preconditioning. New adaptive control techniques for the block numbers and block sizes suggest a gain in efficiency, which should be demonstrated for application problems such as the self-consistent field iterations in the quantum mechanical density functional theory.