Convergence of Restarted Krylov Subspaces to Invariant Subspaces
Authors:
- Christopher BeattieCBChristopher Beattie
- Mark EmbreeMEMark Embree
- John RossiJRJohn Rossi
- Mark Embree Christopher BeattieMBMark Embree Christopher Beattie
- Petros DrineasPDPetros Drineas
- Ilse C. F. IpsenIIIlse C. F. Ipsen
- Eugenia-Maria KontopoulouEKEugenia-Maria Kontopoulou
- Malik Magdon-IsmailMMMalik Magdon-Ismail
- Ronald B. MorganRMRonald B. Morgan
- Huy V. NguyenHNHuy V. Nguyen
- 1 January 2004
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 25 (4) , 1074-1109
Abstract
The performance of Krylov subspace eigenvalue algorithms for large matrices can be measured by the angle between a desired invariant subspace and the Krylov subspace. We develop general bounds for this convergence that include the effects of polynomial restarting and impose no restrictions concerning the diagonalizability of the matrix or its degree of nonnormality. Associated with a desired set of eigenvalues is a maximum "reachable invariant subspace" that can be developed from the given starting vector. Convergence for this distinguished subspace is bounded in terms involving a polynomial approximation problem. Elementary results from potential theory lead to convergence rate estimates and suggest restarting strategies based on optimal approximation points (e.g., Leja or Chebyshev points); exact shifts are evaluated within this framework. Computational examples illustrate the utility of these results. Origins of superlinear effects are also described.Keywords
This publication has 34 references indexed in Scilit:
- An analysis of the Rayleigh–Ritz method for approximating eigenspacesMathematics of Computation, 2000
- Templates for the Solution of Algebraic Eigenvalue Problems2000
- Krylov sequences of maximal length and convergence of GMRESBIT Numerical Mathematics, 1998
- Nested Lanczos: implicitly restarting an unsymmetric Lanczos algorithmNumerical Algorithms, 1998
- From Potential Theory to Matrix Iterations in Six StepsSIAM Review, 1998
- Model reduction of state space systems via an implicitly restarted Lanczos methodNumerical Algorithms, 1996
- The Convergence of Generalized Lanczos Methods for Large Unsymmetric EigenproblemsSIAM Journal on Matrix Analysis and Applications, 1995
- Bounds on the error of an approximate invariant subspace for non-self-adjoint matricesNumerische Mathematik, 1994
- Estimation of Iterated Matrices, with application to the von Neumann conditionNumerische Mathematik, 1960
- The principle of minimized iterations in the solution of the matrix eigenvalue problemQuarterly of Applied Mathematics, 1951