Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Practical divide-and-conquer algorithms for polynomial arithmetic

Tools
- Tools
+ 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. doi:10.1007/978-3-642-23568-9_16 ISSN 0302-9743.

[img]
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

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
2011Published
Volume: Vol.6885
Page Range: pp. 200-214
DOI: 10.1007/978-3-642-23568-9_16
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Date of first compliant deposit: 20 December 2015
Date of first compliant Open Access: 20 December 2015
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

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us