| Title | Sparse polynomial division using a heap |
| Author(s) | Michael Monagan, Roman Pearce |
| Type | Article in Journal |
| Abstract | In 1974, Johnson showed how to multiply and divide sparse polynomials using a binary heap. This paper introduces a new algorithm that uses a heap to divide with the same complexity as multiplication. It is a fraction-free method that also reduces the number of integer operations for divisions of polynomials with integer coefficients over the rationals. Heap-based algorithms use very little memory and do not generate garbage. They can run in the CPU cache and achieve high performance. We compare our C implementation of sparse polynomial multiplication and division with integer coefficients to the routines of the Magma, Maple, Pari, Singular and Trip computer algebra systems. |
| Keywords | Sparse polynomials, Polynomial multiplication, Polynomial division, Polynomial data structures, Heaps |
| ISSN | 0747-7171 |
| URL |
http://www.sciencedirect.com/science/article/pii/S0747717110001446 |
| Language | English |
| Journal | Journal of Symbolic Computation |
| Volume | 46 |
| Number | 7 |
| Pages | 807 - 822 |
| Year | 2011 |
| Note | Special Issue in Honour of Keith Geddes on his 60th Birthday |
| Edition | 0 |
| Translation |
No |
| Refereed |
No |
