Commutative Gröbner Basis Algorithms (GBA) can be used to systematically eliminate variables from a collection of polynomial equations (e.g., ) so as to put it in triangular form. One specifies an order on the variables ( ) which corresponds to ones priorities in eliminating them. Here the GBA will try hardest to eliminate and try the least to eliminate . The output is a list of equations in a ``canonical form'' which is triangular:
Here the polynomials generate the same ideal that the polynomials do. Therefore, the set of solutions to the collection of the polynomial equations equals the set of solutions to the collection of polynomial equations . This canonical form greatly simplifies the task of solving the collection of polynomial equations by facilitating backsolving for in terms of . The effect of the ordering on the variables is to specify that variables high in the order will be eliminated while variables low in the order will not be eliminated.
In the noncommutative case, Gröbner Basis algorithms exist ([FMora]). One can define lexicographic and lexicographic-like term orders (see § and Appendix §). Again, a Gröbner Basis for a collection of polynomial equations is a collection of noncommuting polynomial equations in triangular form (see Theorem 11.3). There are some difficulties which don't occur in the commutative case. For example, a Gröbner Basis can be infinite in the noncommutative case (see § for a way to counteract this effect). However, we believe that noncommutative Gröbner Basis may prove to be extremely useful, see [HW] or [HSW], for applications to simplification of complicated expressions. As we shall see, the present paper concerns a different type of application, that of eliminating unknowns from collections of equations, which is the main function of the NCProcess commands.
In this paper, Gröbner Bases are computed using an algorithm in [TMora]. See also § for further discussion. We use the abbreviations GB and GBA to refer to Gröbner Basis and Gröbner Basis Algorithm respectively. Since we will not always let the GBA run until it finds a Gröbner Basis, we will often be dealing with sets which are not Gröbner Bases, but rather intermediate results. We call such sets of polynomial equations partial GB's.