A Practical Univariate Polynomial Composition Algorithm - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

A Practical Univariate Polynomial Composition Algorithm

(1) , (2, 3)
1
2
3

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.
Fichier principal
Vignette du fichier
dmtcs_NOVOCIN2010.pdf (111.16 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ensl-00546102 , version 1 (13-12-2010)

Identifiers

  • HAL Id : ensl-00546102 , version 1

Cite

William Hart, Andrew Novocin. A Practical Univariate Polynomial Composition Algorithm. 2010. ⟨ensl-00546102⟩
365 View
1648 Download

Share

Gmail Facebook Twitter LinkedIn More