Some comments on term-ordering in Gröbner basis computations
William Yu Sit · ACM SIGSAM Bulletin · 1989
As is well-known, both the theoretical properties of Gröbner basis and the efficiency of Gröbner basis computations using Buchberger's algorithm depend on a particular choice of term-ordering (see Buchberger, [1987] and Böge, et al , [1986]). While all admissible term-orderings has been characterized (Robbiano, [1985] and [1988]; Weispfenning, [1987]), the term-orderings that are commonly used in the literature and in computer algebra systems do not yet have a unified terminology. Thus we have total-degree ordering, purely lexicographical ordering (Buchberger, [1985]), lexicographical ordering (Buchberger, [1976]; Bayer and Stillman, [1987]), reverse lexicographical ordering (Jenks, [1984]; Bayer and Stillman, [1987]), and inverse graduated term-ordering and inverse lexicographical term-ordering (Böge, et al [1986]). Some other authors have used these terms without defining them, and since the same terminology may actually mean different orderings, a reader has to guess at the correct interpretation. Thus a researcher who wants to implement an algorithm based on a theoretical result which depends on a particular term-ordering may inadvertently use a different term-ordering. Worse yet, a user of such a program may not even be aware of the wrong term-ordering used. I think this problem should be brought to the attention of the Gröbner basis research community.