In this paper we present a novel matrix method for polynomial rootfinding. By exploiting the properties of the QR eigenvalue algorithm applied to a suitable CMV-like form of a companion matrix we design a fast and computationally simple structured QR iteration.
A fast implicit QR algorithm for eigenvalue computation of low rank corrections of unitary matrices is adjusted to work with matrix pencils arising from polynomial zerofinding problems . The modified QZ algorithm computes the generalized eigenvalues
of certain NxN rank structured matrix pencils using O(N^2) ops and O(N) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.
