The Library
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. ISSN 0302-9743. doi:10.1007/978-3-642-23568-9_16
|
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, 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: |
|
||||
| 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 | ||||
| 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 |
Downloads
Downloads per month over past year
