A multishift QR iteration without computation of the shifts (Q1334239)

This paper introduces an algorithm that produces the shift vector for multishift QR from the evaluation of the characteristic polynomial of a Hessenberg matrix, thus avoiding the computation of eigenvalues of the trailing principal submatrix of order \(m\) (the number of shifts of the origin of the spectrum in each step required to control convergence) of the iterated matrix, as it is necessary in the multishift QR iteration by \textit{Z. Bai} and \textit{J. Demmel} [Int. J. High Speed Comput. 1, No. 1, 97-112 (1989; Zbl 0726.65035)]. The present algorithm is stable, more accurate, faster, and simpler than the other. It is a matrix extension of \textit{M. A. Hyman's} method [Eigenvalues and eigenvectors of general matrices. 12th ACM National Meeting, Houston, TX (1957)]. Experiments to confirm those claims were done on an HP 9000/720 work- station (IEEE double precision) for Hessenberg matrices with entries uniformly distributed on \((-1,1)\) and for orthogonally Hessenberg-reduced matrices with entries distributed as before, typically for runs between \(n= 100\) and 300 steps and \(m\leq n/2\). The improvement on time of a QR eigenvalue solver was relatively modest. The new scheme extends to the generalized eigenproblem.