  This work is a comprehensive extension of Abu-Salem et al. (2015) that
investigates the prowess of the Funnel Heap for implementing sums of products
in the polytope method for factoring polynomials, when the polynomials are in
sparse distributed representation. We exploit that the work and cache
complexity of an Insert operation using Funnel Heap can be refined to de- pend
on the rank of the inserted monomial product, where rank corresponds to its
lifetime in Funnel Heap. By optimising on the pattern by which insertions and
extractions occur during the Hensel lifting phase of the polytope method, we
are able to obtain an adaptive Funnel Heap that minimises all of the work,
cache, and space complexity of this phase. Additionally, we conduct a detailed
empirical study confirming the superiority of Funnel Heap over the generic
Binary Heap once swaps to external memory begin to take place. We demonstrate
that Funnel Heap is a more efficient merger than the cache oblivious k-merger,
which fails to achieve its optimal (and amortised) cache complexity when used
for performing sums of products. This provides an empirical proof of concept
that the overlapping approach for perform- ing sums of products using one
global Funnel Heap is more suited than the serialised approach, even when the
latter uses the best merging structures available.
