Convergence of Restarted Krylov Subspaces to Invariant Subspaces

From MaRDI portal





The authors prove estimates for the angle (strictly spoken: for the containment gap) between a searched invariant subspace of a general \(n\times n\) matrix and the subspace generated by Krylov subspace methods like the Arnoldi algorithm or the biorthogonal Lanczos algorithm. They don't make further assumptions on the matrix and take into account restarts (by writing the new starting vector as \(p(A)v\) where \(p\) is a suitable polynomial and \(v\) the former starting vector). Their estimates contain 3 constants and an expression which can be further estimated by inserting an appropriate polynomial of given degree. Here, polynomials turn out to be advantageous which take on small values on a set in the complex plane containing all unwanted eigenvalues and large values for a set containing the wanted eigenvalues. The optimal polynomial is shown to be connected to the solution of a Zolotarev-type approximation problem. From the 3 constants in the gap estimate, one is at most \(\sqrt 2\), the remaining two are closely further estimated by appropriate singular values and using pseudospectra bounds. The theory developed is able to explain convergence behaviour including stagnation and superlinear phases, and to suggest optimal restart strategies. A series of numerical experiments for matrices with known Jordan structure shows that the estimates are rather close and can deliver convergence rates with small error.




Cited in
(28)


Describes a project that uses

Uses Software






This page was built for publication: Convergence of Restarted Krylov Subspaces to Invariant Subspaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4650974)