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 (`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`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).