Alternatives in Implementing Noncommutative Grobner Basis Systems

Abstract

Alternatives in implementing systems for computing Grobner bases in path algebras (noncommutative polynomial rings) are considered and compared. Adapted forms of the standard variations to the Buchberger's algorithm (for commutative polynomial rings) are discussed, as is a pattern matching approach that finds the divisors and common multiples among the leading terms of a set of polynomials. Results from preliminary experimentation with a prototype system are used to compare the different configurations of two variations (triple elimination and basis reduction). Eight problem instances split between two classes of problems (one over free algebras, the other over mesh algebras) are used to compare the configurations. An informal analysis suggests that order plays a larger role in determining the execution time for a problem instance that the algorithm. However, by comparing configurations for each of the admissible orders, some observations can be made about the algorithms.