Compression of unitary rank-structured matrices to CMV-like shape with an application to polynomial rootfinding

This paper is concerned with the reduction of a unitary matrix UU to CMV-like shape. A Lanczos-type algorithm is presented which carries out the reduction by computing the block tridiagonal form of the Hermitian part of UU, i.e., of the matrix U+UHU+UH. By elaborating on the Lanczos approach we also propose an alternative algorithm using elementary matrices which is numerically stable. If UU is rank-structured then the same property holds for its Hermitian part and, therefore, the block tridiagonalization process can be performed using the rank-structured matrix technology with reduced complexity. Our interest in the CMV-like reduction is motivated by the unitary and almost unitary eigenvalue problem. In this respect, finally, we discuss the application of the CMV-like reduction for the design of fast companion eigensolvers based on the customary QR iteration.