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.