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*.

Wed Jul 3 10:27:42 PDT 1996