Sparse polynomial division using a heap |
| |
Authors: | Michael Monagan Roman Pearce |
| |
Affiliation: | Department of Mathematics, Simon Fraser University, Burnaby B.C. V5A 1S6, Canada |
| |
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 |
本文献已被 ScienceDirect 等数据库收录! |