2 monomial representations

As a first question, one might wonder which kind of polynomial (and, consequently, monomial) representation is best suited for GB computations. Although there are several alternatives to choose from (e.g., distributive/recursive, sparse/dense), it is generally agreed upon that efficiency considerations lead to only one real choice: a dense distributive representation. That is, a polynomial is stored as a sequence of terms where each term consists of a coefficient and an array of exponents which encodes the respective monomial. With such a representation, one has not only very efficient access to the leading monomial of a polynomial (which is the most frequently needed part of a polynomial during GB computations), but also to the single (exponent) values of a monomial.

Now, what type should the exponent values have? Efficiency considerations lead again to only one realistic choice, namely to fixed-length integers whose size is smaller or equal to the size of a machine word. While assuring the most generality, operations on and representations of arbitrary-length exponent values usually incur an intolerable slow-down of GB computations. Of course, a fixed-length exponent size restricts the range of representable exponent values. However, exponent bound restrictions are usually not very critical for GB computations: on the one hand, the (worst case) complexity of GB computations grows exponentially with the degree of the input polynomials, i.e., large exponents usually make a problem practically uncomputable. On the other hand, checks on bounds of the exponent values can be realized by degree bound checks in the outer loops of the GB computation (e.g., during the S-pair selection) which makes exponent value checks in subsequent monomial operations unnecessary.

Furthermore, the degree of a monomial is so often needed during GB computations, that, as experience has shown, it is advantageous to add an additional degree field to the monomial data structure.

As an illustration, and for later reference, we show below SINGULAR's internal Term_t data structure:

struct  Term_t
{
  Term_t*     next; 
  void*       coef;  
  long        order; 
  Exponent_t  exp[1];
};

Following the arguments outlined above, a SINGULAR polynomial is represented as a linked list of terms, where each term consists of a coefficient (implemented as a hidden type: could be a pointer or a long) and a monomial. A monomial is represented by its exponent vector, together with its degree field (order). The data type of the exponent values (Exponent_t) can be set at configuration time with the restriction that it must be an integer type whose size is a multiple of the word size of the used machine. The size of the Term_t structure is dynamically set at run-time, depending on the number of variables in the current polynomial ring.

Based on a monomial representation like SINGULAR's, the basic monomial operations are ``traditionally'' implemented by straightforward realizations of their definitions. Only monomial additions need also to update the order field of the result monomial, which is simply accomplished by adding the degree values of the operands (since the values of the order-field are additive).