Unfortunately, the Buchberger algorithm and its variants have a worst case exponential time and space complexity [2]. Consequently, GB computations have limited practicality and tend to tremendously long running times and consumptions of huge amounts of memory. For these reasons, a large amount of work has been done to try to improve the (time and space) efficiency of GB computations (see, for example, [7,8,10]). Most of this work resulted in algorithmic improvements which led to more manageable computations for many classes of problems. Our approach to improving the efficiency of GB computations is somewhat different: instead of trying to improve algorithmic aspects of GB computations we take the algorithms more or less as they are and study efficient ways to implement them.
Analyzing GB computations from an implementation point of view leads to many interesting questions. For example: What is the best way to implement coefficient arithmetic? How should polynomials and monomials be represented and their operations be implemented? How should memory management be realized?
Apart from some exceptions (for example, [1]), these questions have not yet received a lot of systematic research and literature attention. Nevertheless, work in this direction can be very fruitful, as we report in this article. We concentrate on monomials - the most frequently used primitive data in GB computations - and show that improvements in the representation of and operations on monomials can lead to significant efficiency gains of GB computations.
In Section 2 we discuss the basics of monomial operations and representations. In Section 3 we investigate vectorized monomial operations, which handle more than one exponent at a time. In section 4 we examine a rank-based representation of monomials, which encodes the exponent vector as one single integer for the purpose of expediting monomial comparisons. In both of these sections, we give extended sets of timings which show the effects of the respective concepts. Finally, we summarize our results in Section 5 and give more details about our used benchmark examples in the Appendix.
We used the Computer Algebra System (CAS) SINGULAR [11] to implement, examine and benchmark the techniques discussed in this paper. SINGULAR is CAS for polynomial computations with special emphasize on the needs of Commutative Algebra, Algebraic Geometry, and Singularity Theory. It features, among others, one of the fastest and most general implementation of GB computations and was therefore an ideal test-bed for our experiments.