Fast computation of eigenvalues of companion, comrade, and related matrices (Q2450887)

Roots of polynomials can be found as the eigenvalues of its companion matrix. If the polynomial is written as a linear combination of polynomials of increasing degree satisfying a (short) recurrence relation, one has to compute the eigenvalues of a band matrix (recurrence) with a spike (e.g., the first row may have all the coefficients). This paper proposes a method to solve these special eigenvalue problems while storing the matrix in factored form (essentially a sequence of \(2\times2\) matrices), requiring \(O(n)\) storage and solving it in \(O(n)\) operations. What is gained in efficiency is lost in stability. The method is a structure preserving implicitly shifted \(LR\) factorization. So eventually a quality control is essential, which fortunately also provides information to efficiently add a Newton iteration. Numerical tests illustrate that the methods are faster than previous code of the authors [SIAM J. Sci. Comput. 35, No. 1, A255--A269 (2013; Zbl 1264.65074)], but the double-shift version is too unstable, so that only the single-shift version with Newton step is of practical use.