ACCELERATING CONVERGENCE BY AUGMENTED RAYLEIGH-RITZ PROJECTIONS FOR LARGE-SCALE EIGENPAIR COMPUTATION

作者：Wen, Zaiwen^*; Zhang, Yin

来源：SIAM Journal on Matrix Analysis and Applications, 2017, 38(2): 273-296.

DOI：10.1137/16M1058534

• extreme eigenpairs
• power method
• Rayleigh-Ritz procedure

Iterative algorithms for large-scale eigenpair computation of symmetric matrices are mostly based on subspace projections consisting of two main steps: a subspace update (SU) step that generates bases for approximate eigenspaces, followed by a Rayleigh-Ritz projection step that extracts approximate eigenpairs. A predominant methodology for the SU step makes use of Krylov subspaces and builds orthonormal bases piece by piece in a sequential manner. On the other hand, block methods such as the classic (simultaneous) subspace iteration, allow higher levels of concurrency than what is reachable by Krylov subspace methods, but may suffer from slow convergence. In this work, we analyze the rate of convergence for a simple block algorithmic framework that combines an augmented Rayleigh-Ritz (ARR) procedure with the subspace iteration. Our main results are Theorem 4.5 and its corollaries, which show that the ARR procedure can provide significant accelerations to convergence speed. Our analysis will offer useful guidelines for designing and implementing practical algorithms from this framework.

• 出版日期2017
• 单位北京大学