A Practical Univariate Polynomial Composition Algorithm

William Hart 1 Andrew Novocin 2, 3
3 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We revisit a divide-and-conquer algorithm, originally described by Brent and Kung for composition of power series, showing that it can be applied practically to composition of polynomials in Z[x] given in the standard monomial basis. We offer a complexity analysis, showing that it is asymptotically fast, avoiding coefficient explosion in Z[x]. The algorithm is straightforward to implement and practically fast, avoiding computationally expensive change of basis steps of other polynomial composition strategies. The algorithm is available in the open source FLINT C library and we offer a practical comparison with the polynomial composition algorithm in the MAGMA computer algebra system.
Type de document :
Pré-publication, Document de travail
Submitted to Journal DMTCS. 2010
Liste complète des métadonnées

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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00546102
Contributeur : Andrew Novocin <>
Soumis le : lundi 13 décembre 2010 - 16:20:13
Dernière modification le : mardi 16 janvier 2018 - 15:50:52
Document(s) archivé(s) le : lundi 5 novembre 2012 - 13:30:56

Fichier

dmtcs_NOVOCIN2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00546102, version 1

Collections

Citation

William Hart, Andrew Novocin. A Practical Univariate Polynomial Composition Algorithm. Submitted to Journal DMTCS. 2010. 〈ensl-00546102〉

Partager

Métriques

Consultations de la notice

605

Téléchargements de fichiers

962