The Geobucket Data Structure for Polynomials
Tongjiang Yan · Journal of Symbolic Computation · 1998
Thegeobucketdata structure is a suitable intermediate representation of polynomials for performing large numbers of polynomial additions in the face of interspersed lead-term extractions. A sum involvingNterms has worst-case running timeO(N log N), matching or surpassing the performance of lists and binomial heaps. This makes the geobucket a good choice for performing reductions in Gröbner basis computations.