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 metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00546102
Contributor : Andrew Novocin <>
Submitted on : Monday, December 13, 2010 - 4:20:13 PM
Last modification on : Thursday, January 17, 2019 - 3:16:03 PM
Long-term archiving on : Monday, November 5, 2012 - 1:30:56 PM

File

dmtcs_NOVOCIN2010.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ensl-00546102, version 1

Collections

Citation

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

Share

Metrics

Record views

747

Files downloads

1375