Dynamics of the symmetric eigenvalue problem with shift strategies

Abstract

A common algorithm for the computation of eigenvalues of real symmetric tridiagonal matrices is the iteration of certain special maps $F_{\sigma }$ called shifted $QR$ steps. Such maps preserve spectrum and a natural common domain is ${\mathcal{T}}_{\Lambda }$, the manifold of real symmetric tridiagonal matrices conjugate to the diagonal matrix $\Lambda$. More precisely, a (generic) shift $s \in \RR$ defines a map $F_s:{\mathcal{T}}_{\Lambda }\to {\mathcal{T}}_{\Lambda }$. A strategy $σ: {\cal T}_Λ\to \RR$ specifies the shift to be applied at $T$ so that $F_{\sigma }(T)=F_{\sigma (T)}(T)$. Good shift strategies should lead to fast deflation: some off-diagonal coordinate tends to zero, allowing for reducing of the problem to submatrices. For topological reasons, continuous shift strategies do not obtain fast deflation; many standard strategies are indeed discontinuous. Practical implementation only gives rise systematically to bottom deflation, convergence to zero of the lowest off-diagonal entry $b(T)$. For most shift strategies, convergence to zero of $b(T)$ is cubic, $|b(F_{\sigma }(T))|=\Theta (|b(T){|}^k)$ for $k=3$. The existence of arithmetic progressions in the spectrum of $T$ sometimes implies instead quadratic convergence, $k=2$. The complete integrability of the Toda lattice and the dynamics at non-smooth points are central to our discussion. The text does not assume knowledge of numerical linear algebra.

22 pages, 4 figures. This preprint borrows heavily from the unpublished preprint arXiv:0912.3376 but is adapted for a different audience

References in corpus (4)

• The Asymptotics of Wilkinson's Iteration: Loss of Cubic Convergence
• An atlas for tridiagonal isospectral manifolds
• The asymptotics of Wilkinson's shift iteration
• Parametrization by polytopes of intersections of orbits by conjugation

Cited by in corpus (2)

• Linearizing Toda and SVD flows on large phase spaces of matrices with real spectrum
• An atlas adapted to the Toda flow