Alternatives in Implementing Noncommutative Gröbner Basis Systems
Benjamin J. Keller · Birkhäuser Basel eBooks · 1998
Alternatives in implementing systems for computing Gröbner bases of two-sided ideals in noncommutative algebras (presented as path algebras) 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 set 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 than the algorithm. However, by comparing configurations for each of the admissible orders, some observations about the algorithms can be made. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.