Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleSparse polynomial division using a heap
Author(s) Michael Monagan, Roman Pearce
TypeArticle in Journal
AbstractIn 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.
KeywordsSparse polynomials, Polynomial multiplication, Polynomial division, Polynomial data structures, Heaps
URL http://www.sciencedirect.com/science/article/pii/S0747717110001446
JournalJournal of Symbolic Computation
Pages807 - 822
NoteSpecial Issue in Honour of Keith Geddes on his 60th Birthday
Translation No
Refereed No