next up previous contents
Next: Recipes Up: Gröbner bases and Previous: Gröbner bases and

Definitions

Temporary Working Definition: A Gröbner basis of a set of multivariate polynomials

where (note necessarily), is an equivalent but `more convenient' set of multivariate polynomials

where t may not be the same as n or m, necessarily. We usually find Gröbner bases by use of computer algebra.

More details will be given on what we mean by `equivalent' and `more convenient', later.

Remark. Gröbner bases are computed with respect to a monomial ordering. That is, we need to be able to compare to xy or and decide which is `first'. There are several standard monomial orderings in the theory of Gröbner bases. The two maple uses are

  1. plex or `Pure Lexicographic' ordering. The standard name for this is simply `lexicographic' order. It is familiar to everyone who can use a dictionary or phone book. Suppose we use the variables with the implicit ordering . This means is the `most important' variable, say, down to , the `least important'. (These emotionally-charged words don't really mean anything, it's just a way of distinguishing). Of course if we start with x, y, z we can always rename so this ordering reflects our priorities (though often the choice of ordering among variables is arbitrary).

    Now consider the monomial term , which we use as shorthand for , and the monomial term (which is a similar shorthand, of course). We say that in the lexicographic order if the LEFTMOST nonzero entry in the vector is POSITIVE. Thus since . So a lexicographic ordering counts powers of x as being more important than powers of other terms (making the identification , of course).

  2. tdeg or `total degree'. The standard name for this is `graded reverse lexicographic order', and the emphasis is on the first two words. The `graded' means that we consider total degree first: if ---that is, if the sum of the powers is larger, then that's the larger term. If we have a tie in powers (e.g. vs ) then we have to resort to a tie-breaking rule: it turns out to be useful to consider REVERSE lexicographic order, which says that if the RIGHTMOST nonzero entry of is NEGATIVE. Note the double-negative from pure lexicographic order, but it is the grading from the sums of powers that turns out to be most significant. Then since the total degree of the second term is higher. Also, since .
We use only well-orderings: exactly one of s > t, s=t, or s < t can hold. Remark. Lexicographic order gives the simplest answers, but it turns out to be (naturally) the hardest one to compute. There are other orderings than these ones, some of which are implemented in other computer algebra systems.

next up previous contents
Next: Recipes Up: Gröbner bases and Previous: Gröbner bases and



Robert Corless
Tue Mar 12 21:09:19 EST 1996