The Restarted QR-Algorithm for Eigenvalue Computation of Structured Matrices

The QR-algorithm is a popular numerical method for the computation of eigenvalues of matrices. All eigenvalues of a general n n upper Hessenberg matrix typically can be computed in O(n ) arithmetic oating point operations using O(n ) storage locations. When the upper Hessenberg matrix is Hermitian or unitary, then it can be represented by O(n) parameters, and there are variants of the QR-algorithm that reduce the operation count for computing all eigenvalues to ) arithmetic oating point operations and the storage requirement to O(n) locations. However, for many structured matrices that can be represented with O(n) storage locations, available implementations of the QR-algorithm require O(n ) arithmetic oating point operations and O(n storage locations to determine all eigenvalues. This note shows that for some of the latter matrices, the operation count can be reduced to O(n ) arithmetic oating point operations and the memory requirement to O(n) storage locations by periodically restarting the QR-algorithm