Dynamics of the symmetric eigenvalue problem with shift strategies

Mathematics – Dynamical Systems

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

Scientific paper

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 ${\cal 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: {\cal T}_\Lambda \to {\cal T}_\Lambda$. A strategy $\sigma: {\cal T}_\Lambda \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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Dynamics of the symmetric eigenvalue problem with shift strategies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamics of the symmetric eigenvalue problem with shift strategies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamics of the symmetric eigenvalue problem with shift strategies will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-729122

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.