Convergence of Restarted Krylov Subspaces to Invariant Subspaces (Q4650974)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2135299
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Convergence of Restarted Krylov Subspaces to Invariant Subspaces |
scientific article; zbMATH DE number 2135299 |
Statements
Convergence of Restarted Krylov Subspaces to Invariant Subspaces (English)
0 references
21 February 2005
0 references
Krylov subspace methods
0 references
convergence
0 references
containment gap
0 references
restarts
0 references
error bounds
0 references
Arnoldi algorithm
0 references
Lanczos algorithm
0 references
invariant subspaces
0 references
eigenvalues
0 references
pseudospectra
0 references
perturbation theory
0 references
Zolotarev-type polynomial approximation problems
0 references
numerical experiments
0 references
0.8682630658149719
0 references
0.8133885860443115
0 references
0.8068819642066956
0 references
0.7973134517669678
0 references
0.7973134517669678
0 references
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.
0 references