Homepage | Book | Papers | Collaborators | NCAlgebra | Optimization Software

Mora's Algorithm

A Noncommutative Gröbner Basis Package for Mathematica©

This is another package under development which makes use of the NCAlgebra package. What follows is a brief introduction to that package, but more information is available. The entire user manual is available in either dvi or postscript format. The entire source code for this package is also available via anonymous ftp.

This package joins with the package NCAlgebra.m to add powerful automatic methods for handling systems of equations in noncommuting variables. All commutative algebra packages contain commands based on Gröbner Bases and uses of them. For example in Mathematica the Solve command put systems of equations in a "cannonical" form which for simple systems readily yields a solution. Likewise the Mathematica Eliminate command tries to convert a system of equations in unknowns x(1), x(2), ..., x(n) to a "triangular" form in unknowns, that is, a new system of equations like

Here the polynomials {q(j) : j=1,..., k} generate the same ideal that the polynomials {p(j) : 1<= j <= k} do. Therefore, the set of solutions to the system the polynomial equations p(j) = 0 equals the set of solutions to the system of polynomial equations q(j) = 0. This canonical form greatly simplifies the task of solving systems of polynomial equations by allowing one to backsolve for x(j) in terms of {x(1),...,x(j-1)}.A brief mathematical discussion of Gröbner bases appears in the appendix in the NCGB document. The user who is not acquainted at all with Gröbner Basis should still be able to read and use much of the material which is contained within this document. In [FMora], c.f. [TMora], F. Mora described a version of the Gröbner basis algorithm which applied to noncommutative free algebras. We refer to this algorithm as Mora's algorithm. It too puts systems of equations into a "cannonical form" which we believe has considerable possibilities in the noncommutative case. This package implements the Mora algorithm and these applications as well. We think of this package as being useful for at least 4 things.

  1. Simplifying complicated expressions
  2. Making the process of discovering algebraic theorems and appealing formulas semi-automatic
  3. Producing GB's in noncommuting situations
  4. Finding small bases for ideals in a noncommuting algebra
We begin by giving simple examples which are sufficient to show how this package is used. They begin with applications and move to the GB algorithm itself. We then describe the Mathematica commands in subsequent chapters. We refer the user to [HW], [HWS1] and [HWS2] for which describe in detail our approach to simplification of noncommutative expressions. [HS] describes our approach to discovering theorems and formulas as does this document to some extent. Another document describes a version of Mora's algorithm which allows the generation of and the manipulation of infinite collections of polynomials (which are often unavoidable in the noncommutative setting).

Back More Home