next up previous contents
Next: Respect for categories Up: Finding a small generating Previous: Definition of a Gröbner

The RemoveRedundant operation

The third idealized operation which we will consider is called RemoveRedundant and is implementable. RemoveRedundant takes a Gröbner graph tex2html_wrap_inline7574 (with a finite set V) and a set tex2html_wrap_inline7342 and returns the set tex2html_wrap_inline7580 which is determined by the condition that tex2html_wrap_inline7394 if and only if, using the notation of Lemma 12.13, tex2html_wrap_inline7584 is the empty set.

The justification of the use of Remove Redundant requires the following proposition.

Propostion 12.14 Let tex2html_wrap_inline7522 = (V,E) be a Gröbner graph, V be a finite set, tex2html_wrap_inline7342 and X be the set which is generated by RemoveRedundant when it is applied to G and . The ideal generated by equals the ideal generated by X.

Proof. For each tex2html_wrap_inline7602 , let tex2html_wrap_inline7584 be defined as in Lemma 12.13. Since tex2html_wrap_inline7606 , tex2html_wrap_inline7608 . To show that tex2html_wrap_inline7610 , it suffices to show that tex2html_wrap_inline7612 for tex2html_wrap_inline7614 . Let tex2html_wrap_inline7614 . Since tex2html_wrap_inline7618 , tex2html_wrap_inline7584 is not the empty set. Let tex2html_wrap_inline7514 be as in Lemma 12.13. tex2html_wrap_inline7516 is empty for each starting vertex w of tex2html_wrap_inline7514 . By Proposition 12.8, v lies in the ideal generated by the starting vertices of tex2html_wrap_inline7514 and so v lies in the ideal generated by X. This completes the proof of Proposition 12.14.

RemoveRedundant can be a very fast operation since it requires only the searching of graphs (which is fast in comparison to GBA which is what the previous two idealized operations used).



Helton
Wed Jul 3 10:27:42 PDT 1996