5 Summary

In this paper, we examined monomial representations and operations for GB computations. In section 2 we argued that (i) the canonical polynomial representation is a linked list of terms where each term consists of a coefficient, a degree field and an array of fixed-length exponent values, and, that (ii) the canonical implementation of monomial operations is simply the straight-forward realization of their definitions.

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.

We have illustrated with our timings that these advantages directly translate in significant overall speedups of GB computations (which are in the range of 1.5 to 3 in our implementation).

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 $\alpha$ of exponents we keep an additional vector $A \,\alpha$ and accomplish divisibility tests as before, comparisons by vectorized lexicographical comparisons of the $A \,\alpha$ vectors and additions by vectorized additions of both, $\alpha$ and $A \,\alpha$. 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.