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

Elimination

The theory of elimination is well known for the case of commutative Gröbner Basis Algorithms (c.f., [CLS],Ch 3) and we show in Part II in § that it extends in a strong form to the noncommutative case.

Commutative Gröbner Basis Algorithms (GBA) can be used to systematically eliminate variables from a collection of polynomial equations (e.g., tex2html_wrap_inline4522 ) so as to put it in triangular form. One specifies an order on the variables ( tex2html_wrap_inline4524 ) which corresponds to ones priorities in eliminating them. Here the GBA will try hardest to eliminate tex2html_wrap_inline4526 and try the least to eliminate tex2html_wrap_inline4236 . The output is a list of equations in a ``canonical form'' which is triangular:

eqnarray708

Here the polynomials tex2html_wrap_inline4530 generate the same ideal that the polynomials tex2html_wrap_inline4532 do. Therefore, the set of solutions to the collection of the polynomial equations tex2html_wrap_inline4534 equals the set of solutions to the collection of polynomial equations tex2html_wrap_inline4536 . This canonical form greatly simplifies the task of solving the collection of polynomial equations by facilitating backsolving for tex2html_wrap_inline4178 in terms of tex2html_wrap_inline4540 . 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.


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

Helton
Wed Jul 3 10:27:42 PDT 1996