Cluster robust estimates for block gradient-type eigensolvers

Zhou, Ming; Neymeyr, Klaus

doi:10.1090/mcom/3446

Cluster robust estimates for block gradient-type eigensolvers
HTML articles powered by AMS MathViewer

by Ming Zhou and Klaus Neymeyr HTML | PDF

Math. Comp. 88 (2019), 2737-2765 Request permission

Abstract:

Sharp convergence estimates have been derived in recent years for gradient-type eigensolvers for large and sparse symmetric matrices or matrix pairs. An extension of these estimates to the corresponding block iterative methods can be achieved by applying a similar analysis to an embedded vector iteration. Although the resulting estimates are also sharp in the sense that they are not improvable without further assumptions, they cannot reflect the well-known cluster robustness of block eigensolvers. In the present paper, we analyze the cluster robustness of the preconditioned inverse subspace iteration. The main estimate has a weaker assumption and a simpler form compared to some known cluster robust estimates. In addition, it is applicable to further block gradient-type eigensolvers such as the locally optimal block preconditioned conjugate gradient method. The analysis is based on an orthogonal splitting for the block power method and a geometric interpretation of preconditioning. As a by-product, a cluster robust Ritz value estimate for the block power method is improved.

References

Merico E. Argentati, Andrew V. Knyazev, Klaus Neymeyr, Evgueni E. Ovtchinnikov, and Ming Zhou, Convergence theory for preconditioned eigenvalue solvers in a nutshell, Found. Comput. Math. 17 (2017), no. 3, 713–727. MR 3648104, DOI 10.1007/s10208-015-9297-1
Zhaojun Bai, James Demmel, Jack Dongarra, Axel Ruhe, and Henk van der Vorst (eds.), Templates for the solution of algebraic eigenvalue problems, Software, Environments, and Tools, vol. 11, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2000. A practical guide. MR 1792141, DOI 10.1137/1.9780898719581
James H. Bramble, Joseph E. Pasciak, and Andrew V. Knyazev, A subspace preconditioning algorithm for eigenvector/eigenvalue computation, Adv. Comput. Math. 6 (1996), no. 2, 159–189 (1997). MR 1431791, DOI 10.1007/BF02127702
Eugene G. D′yakonov, Optimization in solving elliptic problems, CRC Press, Boca Raton, FL, 1996. Translated from the 1989 Russian original; Translation edited and with a preface by Steve McCormick. MR 1396083
A. V. Knyazev, Sharp a priori error estimates for the Rayleigh-Ritz method with no assumptions on fixed sign or compactness, Mat. Zametki 38 (1985), no. 6, 900–907, 958 (Russian). MR 823428
A. V. Knyazev, Vychislenie sobstvennykh znacheniĭ i vektorov v setochnykh zadachakh: algoritmy i otsenki pogreshnosti, Akad. Nauk SSSR, Otdel Vychisl. Mat., Moscow, 1986 (Russian). MR 1111245
A. V. Knyazev, Convergence rate estimates for iterative methods for a mesh symmetric eigenvalue problem, Soviet J. Numer. Anal. Math. Modelling 2 (1987), no. 5, 371–396. Translated from the Russian. MR 915330
Andrew V. Knyazev, Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput. 23 (2001), no. 2, 517–541. Copper Mountain Conference (2000). MR 1861263, DOI 10.1137/S1064827500366124
Andrew V. Knyazev and Klaus Neymeyr, A geometric theory for preconditioned inverse iteration. III. A short and sharp convergence estimate for generalized eigenvalue problems, Linear Algebra Appl. 358 (2003), 95–114. Special issue on accurate solution of eigenvalue problems (Hagen, 2000). MR 1942725, DOI 10.1016/S0024-3795(01)00461-X
Andrew V. Knyazev and Klaus Neymeyr, Gradient flow approach to geometric convergence analysis of preconditioned eigensolvers, SIAM J. Matrix Anal. Appl. 31 (2009), no. 2, 621–628. MR 2530268, DOI 10.1137/080727567
Klaus Neymeyr, A geometric theory for preconditioned inverse iteration applied to a subspace, Math. Comp. 71 (2002), no. 237, 197–216. MR 1862995, DOI 10.1090/S0025-5718-01-01357-6
Klaus Neymeyr, A posteriori error estimation for elliptic eigenproblems, Numer. Linear Algebra Appl. 9 (2002), no. 4, 263–279. MR 1909253, DOI 10.1002/nla.272
Klaus Neymeyr, A geometric convergence theory for the preconditioned steepest descent iteration, SIAM J. Numer. Anal. 50 (2012), no. 6, 3188–3207. MR 3022259, DOI 10.1137/11084488X
Klaus Neymeyr, Evgueni Ovtchinnikov, and Ming Zhou, Convergence analysis of gradient iterations for the symmetric eigenvalue problem, SIAM J. Matrix Anal. Appl. 32 (2011), no. 2, 443–456. MR 2817498, DOI 10.1137/100784928
Klaus Neymeyr and Ming Zhou, The block preconditioned steepest descent iteration for elliptic operator eigenvalue problems, Electron. Trans. Numer. Anal. 41 (2014), 93–108. MR 3216298
Klaus Neymeyr and Ming Zhou, Convergence analysis of restarted Krylov subspace eigensolvers, SIAM J. Matrix Anal. Appl. 37 (2016), no. 3, 955–975. MR 3529740, DOI 10.1137/16M1056481
Yvan Notay, Convergence analysis of inexact Rayleigh quotient iteration, SIAM J. Matrix Anal. Appl. 24 (2003), no. 3, 627–644. MR 1972671, DOI 10.1137/S0895479801399596
E. Ovtchinnikov, Cluster robustness of preconditioned gradient subspace iteration eigensolvers, Linear Algebra Appl. 415 (2006), no. 1, 140–166. MR 2214750, DOI 10.1016/j.laa.2005.06.039
Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
Heinz Rutishauser, Computational aspects of F. L. Bauer’s simultaneous iteration method, Numer. Math. 13 (1969), 4–13. MR 243730, DOI 10.1007/BF02165269
M. Zhou and K. Neymeyr, Adaptive-Multigrid-Preconditioned (AMP) Eigensolver, Universität Rostock, 2014 (http://www.math.uni-rostock.de/ampe).
Ming Zhou, Convergence estimates of nonrestarted and restarted block-Lanczos methods, Numer. Linear Algebra Appl. 25 (2018), no. 5, e2182, 19. MR 3859159, DOI 10.1002/nla.2182