Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Hart, William B.; Novocin, Andrew (2011)
Publisher: Springer
Languages: English
Types: Unknown
Subjects: QA

Classified by OpenAIRE into

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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • 1. D. Bernstein, Multiprecision Multiplication for Mathematicians, accepted by Advances in Applied Mathematics nd 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 Bezier 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 International 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. AddisonWesley, 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: uni ed superfast algorithms, Springer-Verlag, 2001, pg. 81.
    • 14. V. Shoup NTL: A Library for doing Number Theory, open-source library. http://shoup.net/ntl/
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article