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 sets to the sets C and (see item I3 in §). The union of the 's is the set . Therefore, the union of and the 's is . On the other hand, when NCProcess is given two collections of equations C and , NCProcess computes a finite number of finite sets such that the four properties appearing below hold. Properties 1, 2 and 3 show that a major difference between the 's and the 's is that the union of and the 's is the ideal whereas the union of the 's and is a generating set for the ideal . 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 are equations which depend on exactly j unknowns.

(2) For , is a subset of .

(3) The smallest ideal generated by the union of and the sets 's is .

(4) If there is an equation in 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 above can be related to categories as described in §. In a trivial way, the set 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 's.

Both NCProcess1 and NCProcess2 use algorithms which remove redundant equations (see §) when forming the sets . Given a particular input (see §), the sets which NCProcess1 creates are, in general, different from the sets 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. The output of NCProcess2 is often smaller (and is never larger) than its input.