next up previous contents
Next: Prestrategy Up: NCProcess Previous: Categories

Comparison of NCProcess and Categorize

Structurally, the NCProcess commands act like Categorize, except that Categorize would create an infinite number of sets which are typically infinite and NCProcess creates a finite number of finite sets. The following paragraph makes the above statement more precise.

Categorize associates an infinite number of typically infinite setsgif tex2html_wrap_inline4208 to the sets C and tex2html_wrap_inline4190 (see item I3 in §). The union of the tex2html_wrap_inline4212 's is the set tex2html_wrap_inline4216 . Therefore, the union of tex2html_wrap_inline4200 and the tex2html_wrap_inline4212 's is tex2html_wrap_inline4198 . On the other hand, when NCProcess is given two collections of equations C and tex2html_wrap_inline4190 , NCProcess computes a finite number of finite sets tex2html_wrap_inline4694 such that the four properties appearing below hold. Properties 1, 2 and 3 show that a major difference between the tex2html_wrap_inline4696 's and the tex2html_wrap_inline4212 's is that the union of tex2html_wrap_inline4200 and the tex2html_wrap_inline4212 's is the ideal tex2html_wrap_inline4198 whereas the union of the tex2html_wrap_inline4696 's and tex2html_wrap_inline4190 is a generating set for the ideal tex2html_wrap_inline4198 . Property 4 involves a difference in the way the equations are presented in comparison to the figure in §.

(1) For all j, the elements of tex2html_wrap_inline4696 are equations which depend on exactly j unknowns.
(2) For tex2html_wrap_inline4320 , tex2html_wrap_inline4696 is a subset of tex2html_wrap_inline4198 . gif
(3) The smallest ideal generated by the union of tex2html_wrap_inline4190 and the sets tex2html_wrap_inline4696 's is tex2html_wrap_inline4198 .
(4) If there is an equation in tex2html_wrap_inline4696 which is in the singleton category (see §), then this equation is displayed according to item O1 rather than according to items O4 and O5.

The sets tex2html_wrap_inline4696 above can be related to categories as described in §. In a trivial way, the set tex2html_wrap_inline4696 is precisely the union of V-categories of D where V ranges over all sets of exactly j unknowns and where D is the union of the tex2html_wrap_inline4696 's.

Both NCProcess1 and NCProcess2 use algorithms which remove redundant equations (see §) when forming the sets tex2html_wrap_inline4696 . Given a particular input (see §), the sets tex2html_wrap_inline4696 which NCProcess1 creates are, in general, different from the sets tex2html_wrap_inline4696 which NCProcess2 creates. This is where the two differences between NCProcess1 and NCProcess2 lie. We now describe these two differences. Firstly, NCProcess1 runs a GBA before removing redundant equations, but NCProcess2 does not run a GBA before removing redundant equations. The role of NCProcess2 is to find a smaller generating set -- not to find new equations which hold. Secondly, the algorithm which NCProcess2 uses for removing redundant equations is more aggressive than that of NCProcess1 and, therefore, can take a longer time to execute. NCProcess2 is used only when it is believed that all of the interesting equations for the problem under consideration have been found. NCProcess2 tries to assure that its output has the property that the k-th polynomial on the spreadsheet is not in the ideal generated by the first k-1 polynomials.gif The output of NCProcess2 is often smaller (and is never larger) than its input.

next up previous contents
Next: Prestrategy Up: NCProcess Previous: Categories

Wed Jul 3 10:27:42 PDT 1996