Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations (Q1780608)

The authors present a QR-based root-finder for some specific classes of polynomial and rational equations which runs in linear time per iteration and uses linear memory space. The algorithm computes the eigenvalues of some classes of \(n \times n\) generalized companion matrices by using \({\mathcal{O}}(n)\) arithmetic operations per iteration and with \({\mathcal{O}}(n)\) memory storage. As a main application, by using the already computed eigenvalues the whole set of eigenvectors can be computed efficiently by means of the inverse power method at the cost of \({\mathcal{O}}(n)\) flops per iteration.