Next: Noncommutative elimination theory Up: Algorithms and their properties Previous: Algorithms and their properties

Obtaining smaller Bases; shrinking

Often the Gröbner Basis algorithm gives a generating set for a polynomial ideal which is large enough so that looking for ``interesting'' polynomials can be overwhelming (see §); therefore, it is necessary to find a smaller generating set. It is our belief and experience that most highly algebraic mathematics theorems amount to giving a small generating set for an ideal. This is consistent with the esthetic that one wants simple hypotheses. Also with respect to the use of the theorem for numerics, if one tries to solve redundant equations, then small errors in data and roundoff make the equations contradictory. One reason that one does not seek a minimal (in cardinality) generating set for the ideal is that sometimes one does not want to eliminate certain equations involving knowns (see §). Algorithms for finding small generating sets for ideals is the topic of Part II in §.

We remark to those already familiar with Gröbner Basis that in the case of commutative polynomial rings, if G is a reduced Gröbner Basis, then none of the proper subsets of G is a generating set for the ideal generated by G. In contrast, for the case of noncommutative polynomial rings, a reduced Gröbner Basis is not necessarily a minimal generating set (see Example 12.1). Thus, from a purely mathematical point of view, one natural generalization of a commutative reduced Gröbner Basis is a minimal generating subset of a reduced Gröbner Basis (even though this minimal generating subset is itself not a Gröbner Basis).

Section § discusses the theory behind the algorithms which we use for finding small generating subsets of a given set. These algorithms also pertain to finding minimal generating sets although we do not typically employ them for that purpose.

Next: Noncommutative elimination theory Up: Algorithms and their properties Previous: Algorithms and their properties

Helton
Wed Jul 3 10:27:42 PDT 1996