Letting Homogeneity Entropy Select S-Pairs in Buchberger's Algorithm
For symbolic computation researchers, this work presents a new approach to optimizing Groebner basis computation, though its practical gains are limited to specific data distributions and it is not universally superior.
The paper introduces Homogeneity Entropy, a novel S-pair selection strategy for Buchberger's algorithm that uses an information-theoretic measure based on monomial degree distribution. It outperforms classical strategies on random polynomial systems but underperforms on real-world benchmarks, indicating strategy effectiveness depends on data characteristics.
We present a novel S-pair selection strategy called Homogeneity Entropy, for deciding the sequence of S-polynomials to construct in Buchberger's algorithm to compute a Groebner basis. The strategy uses an information theoretic measure derived from the distribution of degrees among the monomials of the S-polynomial: a very different approach to the classical heuristics such as Degree, Normal and Sugar, or indeed the more recent machine learning approaches to the problem. We implement this strategy and evaluate it on two different datasets: (1) variations of randomly generated polynomial systems with controlled numbers of variables, degrees, and densities; and (2) the PHCpack benchmark dataset sourced from real world problems. The Homogeneity Entropy strategy significantly outperforms classical strategies on random polynomial datasets, but on the PHCpack dataset the classical strategies perform better. This suggests the right strategy varies with the shape of the data and we explore this in several experiments. The new strategy offers practically meaningful gains on certain distributions, and represents the first use of such information-theoretic guidance in the optimisation of symbolic computation algorithms.