The Library
Practical divideandconquer algorithms for polynomial arithmetic
Tools
Hart, William B. and Novocin, Andrew (2011) Practical divideandconquer algorithms for polynomial arithmetic. In: CASC'11 Proceedings of the 13th international conference on Computer algebra in scientific computing, Kassel, Germany, 59 Sep 2011. Published in: Lecture Notes in Computer Science, Vol.6885 pp. 200214.

Text
WRAP_Hart_0584144ma270913polycomp.pdf  Accepted Version Download (460Kb)  Preview 
Official URL: http://dx.doi.org/10.1007/9783642235689_16
Abstract
We investigate two practical divideandconquer 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:  03029743  
Official Date:  2011  
Dates: 


Volume:  Vol.6885  
Page Range:  pp. 200214  
Identification Number:  10.1007/9783642235689_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:  59 Sep 2011  
References:  1. D. Bernstein, Multiprecision Multiplication for Mathematicians, accepted by Advances in Applied Mathematics 

URI:  http://wrap.warwick.ac.uk/id/eprint/43601 
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year