next up previous contents
Next: Gröbner Graph: Background for Up: Finding a small generating Previous: Approximation of the SmallBasis

The ShrinkBasis Operation

The second idealized operation is called ShrinkBasis. For a set tex2html_wrap_inline7128 , ShrinkBasis associates to X every minimal generating subset of X, that is, the collection of all subsets tex2html_wrap_inline7164 such that tex2html_wrap_inline7164 generates the same ideal that X does and no proper subset of tex2html_wrap_inline7164 generates the same ideal that X does. We will denote this collection by ShrinkBasis(X).

One (very inefficient) way to implement ShrinkBasis(X) is by using SmallBasis. Specifically, if we view X as a sequence, the idea is to form

(12.5) {SmallBasis ((X)) : is a permutation of X}.

The result of ShrinkBasis(X) is the set of members of the set of (12.5) such that no subset of it lies in (12.5).

A more efficient way to perform this computation is to determine whether or not x lies in the ideal generated by X\{x} for each x X. ShrinkBasis(X) will be the collection containing the single set X if x is not a member of tex2html_wrap_inline7194 for every x X and otherwise it it the union of all sets ShrinkBasis(X\{x}) such that x X lies in the ideal generated by X\{x}. Of course, one can not determine whether or not an element x is in a specified ideal and so one uses the GBA for a small number of iterations.

Wed Jul 3 10:27:42 PDT 1996