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

Studzinski, Grischa; Zerz, Eva (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013, 2014)
Doktorarbeit

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.

Identifikationsnummern