Computing a Factor of a Polynomial by Means of Multishift <i> LR </i> Algorithms (Q4389067)

This paper is concerned with the problem of the numerical approximation of a factor of degree \(k\) of a polynomial \(p(t)\) of degree \(n\), using the relations between matrix transforms and functional iterations. A representation of the multishift LR matrix iteration in a polynomial setting is established. A globally convergent algorithm for the approximation stated above is obtained. The complexity of the algorithm complemented with a suitable shift strategy is linear with respect to \(n\); moreover, the storage needed is also linear with respect to \(n\). From a computational point of view, the proposed algorithm compares favorably with more traditional approaches based on the reduction to the eigenvalue computation, especially when polynomials of high degree are considered. Numerical experiments are reported and discussed.