In section 3 we introduced the idea of vectorized monomial operations: Instead of working on one exponent at a time, we work with as many exponents at a time, as fit into one machine word (say, m). Vectorized monomial operations can be applied to monomial additions, divisibility tests, assignments, and comparisons w.r.t. simple monomial orderings; and they have the following advantages:
The concept of vectorized monomial comparisons could be extended to non-simple orderings (like elimination, block, or even matrix orderings) based on the following idea: Let A be a matrix describing an arbitrary monomial ordering. Besides representing a monomial by a vector of exponents we keep an additional vector and accomplish divisibility tests as before, comparisons by vectorized lexicographical comparisons of the vectors and additions by vectorized additions of both, and . However, the practicality of this idea remains to be investigated.
In section 4 we examined a rank-based representations of monomials. For degree-based orderings, we can uniquely associate an order-preserving rank with each monomial, and use this rank to reduce a monomial comparisons to just one integer comparison. Unfortunately, our timings indicate that this technique does not generally lead to efficiency gains over vectorized monomial operations, since the time saved in monomial comparisons is usually not enough to make up for the additional time spent in rank computations.
In other words, we highly recommend the usage of vectorized monomial operations in GB computations, whereas we can not recommend rank-based monomial representations and comparisons.
Although parts of our conclusions are based on the timings obtained from a SINGULAR implementation of these techniques, they are system-independent in their nature and should therefor apply in similar ways to other GB implementations.
With our results we have shown that it can be rewarding to systematically examine implementational aspects of GB computations. We hope to continue along these lines and, especially, to get more programmers of the various GB systems to join in such discussions and investigations.