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
      0 references
      0 references
      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 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references