Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Andrew Novocin Connect in order to contact the contributor
Submitted on : Monday, December 13, 2010 - 4:20:13 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Monday, November 5, 2012 - 1:30:56 PM


Files produced by the author(s)


  • HAL Id : ensl-00546102, version 1



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



Record views


Files downloads