Computing a Factor of a Polynomial by Means of Multishift LR Algorithms
Luca Gemignani · SIAM Journal on Matrix Analysis and Applications · 1998
In this paper we deal with the numerical approximation of a factor of a polynomial. Our approach is based on the relations between matrix transforms and functional iterations. We show that a generalized LR algorithm applied to an $n\times n$ Hessenberg matrix A may be viewed in a polynomial setting as an iterative method for the computation of a single factor of arbitrary degree k < n of the characteristic polynomial of A. In its basic form our method is linearly convergent under very mild assumptions. The convergence rate can be improved by considering the technique of shifting; the local convergence of our method complemented with a suitable shift strategy is typically quadratic. One iteration of the resulting algorithm can be performed at the overall cost of O(k 4 + nk 3 ) arithmetical operations and n k 2 log p/p parallel steps with order-pk 2 processors; therefore, it appears to have nice computational features in the typical case where k is a prespecified integer of modest size with respect to n. Moreover, it can be arranged to produce highly efficient parallel algorithms because of its possibility of extensive vectorization. Finally, we confirm its effectiveness by means of numerical experiments which are reported and discussed.