Details:

Title	Alternatives in Implementing Noncommutative Grobner Basis Systems
Author(s)	Benjamin J. Keller
Type	Technical Report, Misc
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.
Length	21
File
URL	http://eprints.cs.vt.edu/archive/00000446/01/TR-96-07.ps
Language	English
Year	1996
Month	January
Edition	0
Translation	No
Refereed	No