Implementation and applications of fundamental algorithms relying on Gröbner bases in free associative algebras

  • Implementation und Anwendungen von fundamentalen Algorithmen, welche auf Gröbner Basen basieren, in der freien, assoziativen Algebra

Studzinski, Grischa; Zerz, Eva (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013, 2014)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2013


In 2009, La Scala and Levandovskyy introduced a new approach for the computation of Gröbner bases of graded ideals in the free associative algebra. The approach utilizes so-called letterplace correspondence and thus the computations take place over a commutative polynomial ring. The latter is very important for applied computer algebra, since data structures and algorithms have been intensively studied in the last 50 years by numerous people. In 2012, La Scala presented the generalized letterplace correspondence for general, not necessarily graded ideals, where the homogenization was used. In this thesis, an alternative approach has been studied, with the aim of direct computations, which do not use homogenization and thus are more eective and less complex. At first, the explicit isomorphism of the free associative algebra to a subalgebra of letterplace ring, equipped with the nonstandard multiplication is given. This lies in the heart of further constructions, data structures, algorithms and implementation. Moreover, the very important question on the presentation of monomial ordering for the free algebra is addressed. The embedding into letterplace ring allows the partial use of Robbiano's Theorem in the latter, resulting in the partial classication of orderings, in particular also of elimination orderings. The images of ideals of the free algebra in the letterplace ring have additional structure, being shift-invariant. The new data structure was developed in order to encode an innite orbit under the action of the shift via the single element and to transfer the fundamental operations into the new setting. Based on this data structure, the algorithms for the computation of a two-sided Gröbner basis of an ideal and of a left Gröbner basis of a left ideal in a nitely presented algebra were designed. Both algorithms are not using homogenization and can be applied to arbitrary ideals. Moreover, algorithms, important in applications, such as the computations of elimination, syzygies, Gel'fand-Kirillov dimension and the upper bound for the global homological dimension were considered and implemented. The data structures and the Gröbner basis algorithms, mentioned above, were thoroughly implemented in the kernel of computer algebra system Singular. The implementation was extensively tested and compared to all major computer algebra systems, featuring similar functionality. The comparison demonstrated, that the implementation competes with and sometimes outperforms the fastest systems available. Further applied algorithms were implemented in Singular libraries. The implemented tools were applied to numerous problems, ranging from group theory (word problem and conjugator search problem for given elements in a given nitely presented group as well as the question of the niteness of the latter group) with interest towards cryptography to the design of new generalized inverses in monoids (due to Drazin). Moreover, the state-of-the-art concerning the applications of generic tools like Grobner bases to some important open problems in computational theory of nitely presented groups is established.