The Library

Practical divide-and-conquer algorithms for polynomial arithmetic

Tools

Hart, William B. and Novocin, Andrew (2011) Practical divide-and-conquer algorithms for polynomial arithmetic. In: CASC'11 Proceedings of the 13th international conference on Computer algebra in scientific computing, Kassel, Germany, 5-9 Sep 2011. Published in: Lecture Notes in Computer Science, Vol.6885 pp. 200-214.

Preview

Text
WRAP_Hart_0584144-ma-270913-polycomp.pdf - Accepted Version
Download (460Kb) | Preview

Official URL: http://dx.doi.org/10.1007/978-3-642-23568-9_16

Abstract

We investigate two practical divide-and-conquer style algorithms for univariate polynomial arithmetic. First we revisit an 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]. Secondly we provide an improvement to Mulders' polynomial division algorithm. 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.

Item Type:

Conference Item (Paper)

Subjects:

Q Science > QA Mathematics

Divisions:

Faculty of Science > Mathematics

Library of Congress Subject Headings (LCSH):

Algorithms, Computer science -- Mathematics

Journal or Publication Title:

Lecture Notes in Computer Science

Publisher:

Springer

ISSN:

0302-9743

Official Date:

2011

Dates:

Date	Event
2011	Published

Volume:

Vol.6885

Page Range:

pp. 200-214

Identification Number:

10.1007/978-3-642-23568-9_16

Status:

Peer Reviewed

Publication Status:

Published

Access rights to Published version:

Restricted or Subscription Access

Funder:

Engineering and Physical Sciences Research Council (EPSRC) , France. Agence nationale de la recherche (ANR)

Grant number:

EP/G004870/1 (EPSRC)

Conference Paper Type:

Paper

Title of Event:

CASC'11 Proceedings of the 13th international conference on Computer algebra in scientific computing

Type of Event:

Conference

Location of Event:

Kassel, Germany

Date(s) of Event:

5-9 Sep 2011

References:

1. D. Bernstein, Multiprecision Multiplication for Mathematicians, accepted by Advances in Applied Mathematics
find at http://cr.yp.to/papers.html#m3, 2001.
2. C. de Boor B-Form Basics, Geometric Modeling: Algorithms and New Trends, SIAM, Philadelphia (1987),
pp. 131{148.
3. A. Bostan and B. Salvy, Fast conversion algorithms for orthogonal polynomials, Preprint.
4. H.Prautzsch, W.Boehm, and M.Paluszny Bézier and B-Spline Techniques, Springer, 2002.
5. R. Brent and H.T. Kung, O((n log n)3=2) Algorithms for composition and reversion of power series, Analytic
Computational Complexity, Academic Press, New York, 1975, pp. 217-225.
6. J. J. Cannon, W. Bosma (Eds.) Handbook of Magma Functions, Edition 2.17 (2010)
http://magma.maths.usyd.edu.au/magma
7. J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 1999.
8. G. Hanrot and P. Zimmermann. A long note on Mulder's short product, Journal of Symbolic Computation, v. 37
3 2004, pp. 391{401.
9. W. Hart Fast Library for Number Theory: an introduction, Mathematical Software - ICMS 2010 Third Inter-
national Congress on Mathematical Software, Kobe, Japan, September 13-17, 2010, Proceedings Series: Lecture
Notes in Computer Science, Vol. 6327, pp 88{91. http://www.flintlib.org
10. D. Knuth. The Art of Computer Programming, volume 2: Seminumerical Algorithms, Third Edition. Addison-
Wesley, 1997, pp. 486{488.
11. W. Liu and S. Mann An analysis of polynomial composition algorithms, University of Waterloo Research Report
CS-95-24, (1995).
12. T. Mulders, On Short Multiplications and Divisions, AAECC, vol. 11, 2000, pp. 69{88.
13. V. Pan Structured matrices and polynomials: unified superfast algorithms, Springer-Verlag, 2001, pg. 81.
14. V. Shoup NTL: A Library for doing Number Theory, open-source library. http://shoup.net/ntl/
12