Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices

Let H-n subset of C-n x n be the class of n x n Hessenberg matrices A which are rank-one modifications of a unitary matrix, that is, A = H + uw(H), where H is unitary and u, w is an element of C-n. The class H-n includes three well-known subclasses: unitary Hessenberg matrices, companion (Frobenius) matrices, and fellow matrices. The paper presents some novel fast adaptations of the shifted QR algorithm for computing the eigenvalues of a matrix A is an element of H-n where each step can be performed with O(n) flops and O(n) memory space. Numerical experiments confirm the effectiveness and the robustness of these methods.