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

Studzinski, Grischa; Zerz, Eva

doi:32682

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 (Author)

2013 & 2014

Verantwortlichkeitsangabevorgelegt von Grischa Studzinski

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

Umfang114 S.

Aachen, Techn. Hochsch., Diss., 2013

Zsfassung in dt. und engl. Sprache. - Prüfungsjahr: 2013. - Publikationsjahr: 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Zerz, Eva (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2013-10-18

Online
URN: urn:nbn:de:hbz:82-opus-48603
URL: https://publications.rwth-aachen.de/record/228489/files/4860.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Gröbner-Basis (Genormte SW) ; Freie Algebra (Genormte SW) ; Mathematik (frei) ; Gröbner Basis (frei) ; free algebra (frei) ; letterplace (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 16D25

Kurzfassung
In 2009 stellten La Scala und Levandovskyy einen neuen Weg zur Berechnung von Gröbnerbasen graduierter Ideale in der freien, assoziativen Algebra vor. Dieser Ansatz benutzt die sogenannte Letterplace Korrespondenz und deswegen werden die Berechnungen über einen kommutativen Polynomring ausgeführt. Dieser ist äuerst wichtig für angewandte Computeralgebra, da Datenstrukturen und Algorithmen in den letzten 50 Jahren von zahlreichen Wissenschaftlern intensiv studiert wurden. 2012 präsentierte La Scala die verallgemeinerte Letterplace Korrespondenz für allgemeine, nicht zwingend graduierte Ideale vor, wobei Homogenisierung benutzt wurde. In dieser Arbeit wurde ein alternativer Weg untersucht, mit dem Ziel, direkte Berechnungsverfahren zu entwickeln, welche nicht Homogenisierung nutzen und deswegen eektiver und weniger komplex sind. Zunächst wird ein expliziter Isomorphismus zwischen der freien, assoziativen Algebra und einer Unteralgebra des Letterplace Ringes, welche versehen ist mit einer alternativen Multiplikation, angegeben. Dieser Isomorphismus liegt allen weiteren Konstruktionen, Datenstrukturen, Algorithmen und Implementationen zu Grunde. Darüber hinaus wird die wichtige Frage nach einer Darstellung von Monomordnungen für die freie, assoziative Algebra angesprochen. Die Einbettung in den Letterplace Ring erlaubt eine teilweise Nutzung des Satzes von Robbiano, wodurch eine partielle Klassikation der Ordnungen, insbesondere von Eliminationsordnungen, möglich ist. Die Bilder der Ideale der freien Algebra im Letterplace Ring haben zusätzliche Struktur, denn diese sind shift-invariant. Eine neue Datenstruktur wurde entwickelt, um die unendliche Bahn unter der Shift-Operation mittels eines Elementes darzustellen und um fundamentale Prozeduren in diese neue Situation zu übertragen. Basierend auf dieser Datenstruktur wurden die Algorithmen für die Berechnung einer zwei-seitigen Gröbnerbasis eines Ideals und einer Links-Gröbnerbasis eines Links-Ideals in einer endlich präsentierten Algebra gestaltet. Beide Algorithmen benutzen keine Homogenisierung und können auf beliebige Ideale angewendet werden. Weiterhin wurden weitere Algorithmen, welche für wichtige Anwendungen wie Berechnung von Elimination, Syzygien, Gel'fand-Kirillov Dimension und eine obere Schranke der globalen Dimension benutzt werden, betrachtet und implementiert. Die oben erwähnte Datenstruktur und der Gröbnerbasen Algorithmus wurden sorgfältig in der Kern des Computeralgebra Systems Singular implementiert. Das Programm wurde dann intensiv getestet und mit anderen wichtigen Computeralgebra Systemen verglichen. Dieser Vergleich zeigte, dass die Implementation mit den anderen Systemen mithalten und in einigen Fällen sogar übertreten kann. Die weiteren Algorithmen wurden in Singular Bibliotheken implementiert. Diese neuen Verfahren wurden auf zahlreiche Probleme, reichend vom Bereich der Gruppentheorie (Wort-Problem, Konjugator-Such-Problem für gegebene Elemente einer gegebenen endlich präsentierten Gruppe, sowie die Frage nach der Endlichkeit dieser Gruppe) unter Berücksichtigung kryptographischer Fragestellungen bis hin zur Gestaltung neuer, verallgemeinerter Inversen in Monoiden (gegeben durch Drazin), angewendet. Darüber hinaus wird der Stand der Dinge bezüglich der Anwendbarkeit von generischen Methoden wie Gröbnerbasen auf einige wichtige Probleme der Berechnungen von endlich präsentierten Gruppenneu deniert.

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.

Fulltext:
PDF