Fast QR iterations for unitary plus low rank matrices

Some fast algorithms for computing the eigenvalues of a block companion matrix A=U+XYH, where U∈Cn×n is unitary block circulant and X,Y∈Cn×k, have recently appeared in the literature. Most of these algorithms rely on the decomposition of A as product of scalar companion matrices which turns into a factored representation of the Hessenberg reduction of A. In this paper we generalize the approach to encompass Hessenberg matrices of the form A=U+XYH where U is a general unitary matrix. A remarkable case is U unitary diagonal which makes possible to deal with interpolation techniques for rootfinding problems and nonlinear eigenvalue problems. Our extension exploits the properties of a larger matrix A^ obtained by a certain embedding of the Hessenberg reduction of A suitable to maintain its structural properties. We show that A^ can be factored as product of lower and upper unitary Hessenberg matrices possibly perturbed in the first k rows, and, moreover, such a data-sparse representation is well suited for the design of fast eigensolvers based on the QR/QZ iteration. The resulting algorithm is fast and backward stable