Implicit QR with compression (Q692576)

In some earlier papers the implicit shifted QR-algorithm was introduced and discussed in particular for companion matrices. This method is based on the observation that Hessenberg matrices of the form \(U - pq^T\) where \(U\) is a unitary Hessenberg matrix and \(p,q\) are of rank 1 keep this form under the QR-algorithm. Thus one has an algorithm for finding the roots of a polynomial of degree \(n\) using only \(O(n)\) storage and \(O(n^2)\) flops. In this paper, such an algorithm given in an earlier paper is further simplified and thus speeded up. Extensive numerical experiments are reported which show backward stability, though this property could not yet be proved.