Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial

Victor Y. Pan 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : The known algorithms approximate the roots of a complex univariate polynomial in nearly optimal arithmetic and Boolean time. They are, however, quite involved and require a high precision of computing when the degree of the input polynomial is large, which causes numerical stability problems. We observe that these difficulties do not appear at the initial stages of the algorithms, and in our present paper we extend one of these stages, analyze it, and avoid the cited problems, still achieving the solution within a nearly optimal complexity estimates, provided that some mild initial isolation of the roots of the input polynomial has been ensured. The resulting algorithms promise to be of some practical value for root-finding and can be extended to the problem of polynomial factorization, which is of interest on its own right. We conclude with outlining such an extension, which enables us to cover the cases of isolated multiple roots and root clusters.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Contributeur : Elias Tsigaridas <>
Soumis le : samedi 12 décembre 2015 - 15:38:51
Dernière modification le : jeudi 21 mars 2019 - 14:38:51
Document(s) archivé(s) le : samedi 29 avril 2017 - 12:09:00


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01105267, version 2


Victor Y. Pan, Elias Tsigaridas. Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial. Theoretical Computer Science, Elsevier, 2017. 〈hal-01105267v2〉



Consultations de la notice


Téléchargements de fichiers