Simple and Efficient Real Root-finding for a Univariate Polynomial

Abstract : Univariate polynomial root-finding is a classical subject, still important for modern comput-ing. Frequently one seeks just the real roots of a polynomial with real coefficients. They can be approximated at a low computational cost if the polynomial has no nonreal roots, but for high degree polynomials, nonreal roots are typically much more numerous than the real ones. The challenge is known for long time, and the subject has been intensively studied. Nevertheless, we obtain dramatic acceleration of the known algorithms by applying new combinations of the known algorithms and properly exploiting the geometry of the complex plane. We confirm the efficiency of the proposed real root-finders by both their Boolean complexity estimates and the results of their numerical tests with benchmark polynomials. In particular in our tests the num-ber of iterations required for convergence of our algorithms grew very slowly as we increased the degree of the polynomials from 64 to 1024. Our techniques is very simple, and we point out their further modifications that promise to produce efficient complex polynomial root-finders.
Type de document :
Pré-publication, Document de travail
2015
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01105309
Contributeur : Elias Tsigaridas <>
Soumis le : mardi 20 janvier 2015 - 10:32:30
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mardi 21 avril 2015 - 10:22:56

Fichier

ptz-rf-sub.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01105309, version 1

Collections

Citation

Victor Y. Pan, Elias Tsigaridas, Zhao Liang. Simple and Efficient Real Root-finding for a Univariate Polynomial. 2015. 〈hal-01105309〉

Partager

Métriques

Consultations de la notice

485

Téléchargements de fichiers

309