5 Summary

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:

- 1.
- The maximal number of iterations in the inner loops of the monomial
operations is cut by approximately a factor of
*m*. - 2.
- Non-aligned access of single exponents are avoided.
- 3.
- Monomial comparisons for the different monomial orderings are
reduced to
*one*routine which does not need to explicitly distinguish the different simple monomial orderings.

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.