4 Rank-based monomial representation and comparisons

A different monomial representation is what we call the rank-based representation. This monomial representations was, to the best of our knowledge, first developed for and used in the CAS Macaulay [4]. The main idea behind this monomial representation stems from the following property of a degree based ordering > on M_n:

$$\forall m \in M_n:\char93 \{m^{'}\in M_n: 1 \le m^{'} \le m\} < \infty$$ (5)

Therefore, it is possible to bijectively enumerate the monomials in the order given by the monomial ordering and to represent an entire monomial by just a single integer, which we call the rank of a monomial.

The bijective maps between the monomials and the integers depend on the used monomial ordering: for the degree reverse lexicographic ordering it is given by the following lemma:

Lemma 2: Let $\alpha \in M_n$ and $r_{dp}: M_n \rightarrow \textbf{N}$ given by

$$r_{dp}(\alpha):=\sum_{i=1}^n{\sum_{j=1}^i {\alpha_j+i-1}\choose i}.$$ (6)

Then the following holds:

$$\forall \alpha,\beta\in M_n: r_{dp}(\alpha) > r_{dp}(\beta) \Leftrightarrow \alpha >_{dp} \beta$$

$$\forall \alpha,\beta\in M_n: r_{dp}(\alpha) = r_{dp}(\beta) \Leftrightarrow \alpha = \beta.$$

A similar bijective map can be given for the ordering Dp (degree lexicographic). For negative orderings like Ds or ds the same idea can be exploited but it is necessary to change the signs since the zero monomial is, with respect to these orderings, the largest, not the smallest monomial.

Using the rank-based representation for monomials, monomial comparisons can very easily and efficiently be realized by simply comparing their corresponding ranks (we also call such monomial comparisons simply rank-based comparisons). Furthermore, a pure rank-based polynomial representation is very compact, i.e. requires an almost minimal amount of memory. Unfortunately, we have to pay for these advantages with the following difficulties:

(i)

Monomial additions and divisibility tests can not be easily accomplished, since the bijective enumeration maps are neither additive nor do they allow any direct conclusions about monomial divisibility.

(ii)

An unrestricted realization of the enumeration maps would require that arbitrary precision integers are used which would in turn result in considerable performance losses. On the other hand, restricting the range of the enumeration maps to machine integers, imposes a limit on the largest representable monomial (which we also call the maximal integer monomial). Clearly, this limit depends on the word-length of the machine and on the number of variables of the polynomial ring. For example, using a 32-bit integer for the realization of (6) restricts the degree of the maximal integer monomials as shown in the following table:

variables	3	4	5	7	10	15	20	25
max. deg	2340	471	186	66	31	17	12	9

(iii)

Non-degree orderings (like the lexicographical or negative lexicographical ordering) do not admit a bijective enumeration map which is compatible with the monomial ordering, since they do not enjoy (5).

Problem (i) is overcome in the Macaulay system by keeping two representations of the the leading monomial of a polynomial (the integer representation and the exponent vector representation) and by computing the inverse of the enumeration map for the non-leading monomials of a polynomial.

Problem (ii) is overcome by restricting the input polynomials to being homogeneous and by Macaulay's ``infamous'' degree bound messages and enforcement mechanisms.

Problem (iii) is simply ignored by Macaulay -- no computations with non-degree orderings are possible.

In SINGULAR, we choose a slightly different way to overcome problems (i) - (iii): first, we always keep the exponent vector representation of a monomial. And, second, if a monomial is smaller than the maximal integer monomial, we store its rank in the negative range of the order field (i.e., a->order + INT_MAX yields the rank of the monomial a). If, on the other hand, a monomial is larger than the maximal integer monomial, then its order field contains (as before) the (positive) degree of the monomial.

Based on such a data representation, monomial comparisons can simply be accomplished as follows:

inline long MonComp(Term_t* a, Term_t* b)
{
  if (a->order != b->order)
  {
    if (a->order > b->order) return 1;
    return -1;
  }

  // a->order==b->order: are we already done? 
  if (a->order < 0) return 0;  // monom's are equal

  /* now compare using the exponent values, 
     assuming the degrees are equal ... */
}

 

Table 2: Detailed timings for rank-based monomial operations - same settings as in Table 1.

exponent type	char				short				short
monomial operations	vectorized				vectorized				not vectorized
Example	$$\frac{t_{<}}{t_{r,<}}$$	%R	%comp	$$\frac{t}{t_{r}}$$	$$\frac{t_{<}}{t_{r,<}}$$	%R	%comp	$$\frac{t}{t_{r}}$$	$$\frac{t_{<}}{t_{r,<}}$$	%R	%comp	$$\frac{t}{t_{r}}$$
2mat3	1.3	7.6	69.0	1.1	1.7	6.5	74.4	1.4	1.9	5.0	76.3	1.6
homog gonnet	1.3	6.7	34.5	1.0	1.8	4.7	38.0	1.1	2.7	4.8	43.9	1.3
homog alex 2	1.3	9.7	51.1	0.9	1.4	8.5	51.2	1.0	1.8	7.8	57.4	1.2
alex 2	1.3	7.9	52.1	0.9	1.1	7.4	49.0	1.0	1.6	7.5	56.8	1.2
alex 3	1.3	5.2	47.8	1.0	1.0	2.9	49.1	0.9	1.4	2.8	53.7	1.2
gerhard 1	1.4	15.6	41.9	0.8	1.2	12.8	41.5	0.9	2.0	13.4	48.1	1.2
homog 2mat3	1.2	7.2	70.6	1.0	1.3	4.6	75.4	1.0	1.6	4.1	78.2	1.2
katsura 8	1.4	26.3	39.6	0.8	1.5	25.0	38.5	0.9	2.2	21.6	44.6	1.2
gerhard 2	1.1	10.4	47.4	0.9	1.3	12.6	48.4	0.9	1.7	10.6	54.3	1.1
katsura 7	1.2	28.3	32.7	0.7	1.4	23.0	30.2	0.8	2.1	22.5	38.2	1.1
gerhard 3	1.3	8.0	40.0	0.9	1.5	7.6	43.4	0.9	1.7	7.6	45.4	1.1
homog alex 3	1.2	5.0	39.1	1.0	1.2	5.8	42.0	1.0	1.4	5.8	43.1	1.1
cohn2	1.4	19.6	22.2	0.8	1.3	19.8	23.8	0.9	2.1	19.6	29.9	1.1
bjork 8	1.2	23.6	21.5	0.7	1.6	23.2	21.1	0.8	2.3	21.8	30.1	1.1
cyclic 7	1.3	25.0	22.0	0.8	1.6	22.3	23.8	0.8	2.6	19.6	31.4	1.1
schwarz 11	1.2	20.1	24.4	0.8	1.6	15.9	25.4	0.9	2.2	14.7	30.1	1.1
symmetric 6	1.3	22.1	18.3	0.8	1.5	20.0	19.1	0.9	2.4	18.0	26.9	1.1
schwarz 10	1.2	19.8	20.1	0.8	1.5	15.6	21.1	0.9	2.7	15.5	28.5	1.1
homog cyclic 7	1.4	28.6	24.8	0.7	1.6	24.3	24.2	0.8	2.8	22.0	33.7	1.1
rcyclic 13	1.5	31.1	21.9	0.7	1.7	24.5	19.8	0.9	2.9	19.2	26.1	1.0
rcyclic 14	1.4	28.5	19.1	0.7	2.0	20.3	19.5	0.9	3.5	20.6	27.7	1.0
schwarz 9	1.2	21.2	15.7	0.8	1.4	15.3	18.7	0.9	2.0	16.2	22.4	1.0
rcyclic 12	2.0	25.1	24.2	0.7	1.3	20.1	16.5	0.9	3.1	20.3	24.0	1.0
rcyclic 11	1.4	26.2	21.1	0.7	1.3	23.1	19.1	0.8	3.7	18.7	30.1	1.0
rcyclic 15	1.3	26.2	20.9	0.7	1.5	19.3	20.4	0.9	2.2	17.2	30.3	1.0
homog cyclic 6	1.1	27.3	15.2	0.6	3.1	19.0	32.9	0.8	3.3	19.3	28.0	1.0
gonnet	1.4	7.9	5.6	0.9	1.3	9.3	4.0	0.9	2.3	6.6	9.2	1.0
ecyclic 7*	1.0	3.2	81.4	1.0	1.0	1.7	82.3	1.0	1.0	1.3	84.5	0.9
rcyclic 16*	1.1	17.6	19.4	0.8	1.0	11.8	18.4	0.9	1.0	9.6	26.6	0.9
rcyclic 17*	0.9	15.9	20.5	0.8	0.9	10.8	19.1	0.9	0.9	8.2	27.1	0.9
rcyclic 18*	0.9	15.9	18.2	0.8	1.0	10.0	19.6	0.9	1.0	7.8	29.5	0.9
rcyclic 19*	1.0	16.0	20.4	0.8	1.0	10.1	19.9	0.9	1.1	7.8	29.7	0.9
ecyclic 6*	0.9	18.0	55.3	0.8	1.0	10.9	51.4	0.8	1.2	8.6	66.3	0.8
averages
Pentium Pro	1.3	17.1	33.6	0.8	1.4	13.8	33.8	0.9	2.1	12.6	40.3	1.1
HP C160	1.4	9.1	36.6	0.8	1.6	8.4	39.0	0.9	1.7	9.1	41.6	1.1
DEC Alpha	1.8	11.8	33.1	0.8	1.5	11.7	31.5	0.8	2.4	10.2	35.5	1.0

 

Notice that we do not need to distinguish between the two different interpretations of the order field: if we compare a monomial which is smaller than the maximal integer monomial (order value is negative) with one that is larger (order value is positive), then the different signs of the order fields result in an immediate and correct return of the monomial comparison. Therefore, only a sign-check (for the case of equal order fields) needs to be added to the previously given monomial comparison routines to have them take advantage of ranks.

Since we always keep the exponent vector representation alongside with the ranks, monomial divisibility tests and additions can be accomplished as usual, except that we need to recompute and set the order field at the end of the monomial addition routine. For monomials smaller than the maximal integer monomial, this basically amounts to computations of the respective ranks. We accomplish the latter by a simple implementation of (6) using a pre-computed table of binomial coefficients.

As with vectorized monomial additions, overflow or degree checks can largely be moved to the outer loops of the GB computations so that we can almost always avoid the costly checks on whether or not the sum of two monomials is smaller than the maximal integer monomial.

As a summary, we can conclude that with a relatively small effort, it is possible to extend a ``traditional'' exponent vector-based monomial representation so that it can fully take advantage of ranks while, at the same time, the limitations of the Macaulay system (degree bounds, no support for non-degree orderings, repeated inverse rank computations) can be avoided.

But now again, let us examine some timings (Table 2) to see how much all that buys us in practice: we again used the examples of the Appendix and performed all GB computations using the degree reverse lexicographical ordering (dp) over the coefficient field Z/32003. We obtained timings for three basic SINGULAR configurations: char and short exponents with vectorized monomial operations, and short exponents with ``traditional'' (i.e., not vectorized) monomial operations. For each of these ``conventional'' configurations, we also obtained a SINGULAR version which uses rank-based comparisons and measured the following:

t_<, t_m,<:

the time spent in monomial comparisons, only (t_<-conventional comparisons, t_m,<-rank-based comparisons).

%R, %comp:

the percentage of time spent in rank computations (%R) and in conventional monomial comparisons (%comp).

t, t_r:

the overall running time for the GB computation (t-conventional configuration, t_m-rank-based configuration). For the conventional configuration, these timings are the same as those used in the previous timing, Table 1.

And again, let us see what we can conclude from these experiments:

Firstly, rank-based comparisons are realized substantially faster than traditional and vectorized monomial comparisons (see the t_</t_r,< columns), except in such examples, where a majority of the monomials is larger than the maximal integer monomial (these examples are marked with a *).

Secondly, the time spent for rank computations during monomial additions is significant, and cannot be neglected (see the %R columns).

Thirdly, whether or not the time saved by rank-based comparisons pays off against the additional time spent for rank computations, depends on the relative efficiency of the ``conventional'' monomial comparisons and on the characteristics of the example -- where the percentage of time spent in monomial comparisons seems to be the most important factor (compare the %comp and t/t_r columns).

Finally, evaluating the t/t_r columns, we can conclude good news and bad news: the good news is that rank-based comparisons, by and large, lead to an overall speedup when used in combination with traditional (i.e., not vectorized) monomial operations. That is, our results make a strong case for such a usage of the rank-based representation. The bad news is, that rank-based comparisons by and large do not lead to an overall speedup when used in combination with vectorized monomial operations. Our results show that the more efficient vectorized monomial operations result in smaller speedups of the rank-based comparisons, i.e., speedups which are generally too small to outweigh the additional cost of computing ranks.