zbMATH — the first resource for mathematics

Practical divide-and-conquer algorithms for polynomial arithmetic. (English) Zbl 1308.12007
Gerdt, Vladimir P. (ed.) et al., Computer algebra in scientific computing. 13th international workshop, CASC 2011, Kassel, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23567-2/pbk). Lecture Notes in Computer Science 6885, 200-214 (2011).
Summary: We investigate two practical divide-and-conquer style algorithms for univariate polynomial arithmetic. First we revisit an algorithm originally described by R. P. Brent and H. T. Kung [Anal. comput. Complexity, Proc. Symp. Pittsburgh 1975, 217–225 (1976; Zbl 0342.65010)] for composition of power series, showing that it can be applied practically to composition of polynomials in \(\mathbb Z[x]\) given in the standard monomial basis. We offer a complexity analysis, showing that it is asymptotically fast, avoiding coefficient explosion in \(\mathbb Z[x]\). Secondly we provide an improvement to Mulders’ polynomial division algorithm [T. Mulders, Appl. Algebra Eng. Commun. Comput. 11, No. 1, 69–88 (2000; Zbl 0968.68200)]. We show that it is particularly efficient compared with the multimodular algorithm. The algorithms are straightforward to implement and available in the open source FLINT C library. We offer a practical comparison of our implementations with various computer algebra systems.
For the entire collection see [Zbl 1221.68017].
Reviewer: Reviewer (Berlin)

12Y05 Computational aspects of field theory and polynomials (MSC2010)
65E05 General theory of numerical methods in complex analysis (potential theory, etc.)
68W30 Symbolic computation and algebraic computation
Full Text: DOI