Computing a Factor of a Polynomial by Means of Multishift LR Algorithms

DOI10.1137/S0895479894277442MaRDI QIDQ4389067zbMATH OpenFDO

Authors L. Gemignani

Publication date 11 May 1998

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895479894277442

zbMATH Keywords

algorithmcomplexityeigenvalue computationfactorization of polynomialsfunctional iterationsglobal convergenceLR algorithmsmatrix transformsnumerical experiments

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of solutions to single equations (65H05)

Review text

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.

Recommendations

• Polynomial root computation by means of the LR algorithm
• On One Method for Factorization of Algebraic Polynomials
• Analysis of approximate factorization algorithm. I
• scientific article; zbMATH DE number 1262457

Cited in

(3)

• Polynomial root computation by means of the LR algorithm
• scientific article; zbMATH DE number 5263329 (Why is no real title available?)
• Computing a Hurwitz factorization of a polynomial

Describes a project that uses

Uses Software

• na10

This page was built for publication: Computing a Factor of a Polynomial by Means of Multishift LR Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389067)