The Geobucket Data Structure for Polynomials
Permanent Link(s)
Collections
Author
Yan, Thomas
Abstract
The {\em geobucket/} data structure is suitable as an intermediate representation of polynomials for performing large numbers of polynomial additions and lead term extractions. A sum involving {$N$} terms has worst-case running time {$O(N\log{N})$} both online and offline, matching or surpassing the obvious/standard alternatives. This makes the geobucket a good choice for performing the reduction step of \grobner\ basis computations.
Date Issued
1996-09
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR96-1607
Type
technical report