Non-commutative Computer Algebra for polynomial algebras: Gröbner bases, applications and implementation

Nichtkommutative Computeralgebra für Polynomalgebren: Gröbnerbasen, Anwendungen und Implementierung

  • Non-commutative polynomial algebras appear in a wide range of applications, from quantum groups and theoretical physics to linear differential and difference equations. In the thesis, we have developed a framework, unifying many important algebras in the classes of \(G\)- and \(GR\)-algebras and studied their ring-theoretic properties. Let \(A\) be a \(G\)-algebra in \(n\) variables. We establish necessary and sufficient conditions for \(A\) to have a Poincar'e-Birkhoff-Witt (PBW) basis. Further on, we show that besides the existence of a PBW basis, \(A\) shares some other properties with the commutative polynomial ring \(\mathbb{K}[x_1,\ldots,x_n]\). In particular, \(A\) is a Noetherian integral domain of Gel'fand-Kirillov dimension \(n\). Both Krull and global homological dimension of \(A\) are bounded by \(n\); we provide examples of \(G\)-algebras where these inequalities are strict. Finally, we prove that \(A\) is Auslander-regular and a Cohen-Macaulay algebra. In order to perform symbolic computations with modules over \(GR\)-algebras, we generalize Gröbner bases theory, develop and respectively enhance new and existing algorithms. We unite the most fundamental algorithms in a suite of applications, called "Gröbner basics" in the literature. Furthermore, we discuss algorithms appearing in the non-commutative case only, among others two-sided Gröbner bases for bimodules, annihilators of left modules and operations with opposite algebras. An important role in Representation Theory is played by various subalgebras, like the center and the Gel'fand-Zetlin subalgebra. We discuss their properties and their relations to Gröbner bases, and briefly comment some aspects of their computation. We proceed with these subalgebras in the chapter devoted to the algorithmic study of morphisms between \(GR\)-algebras. We provide new results and algorithms for computing the preimage of a left ideal under a morphism of \(GR\)-algebras and show both merits and limitations of several methods that we propose. We use this technique for the computation of the kernel of a morphism, decomposition of a module into central characters and algebraic dependence of pairwise commuting elements. We give an algorithm for computing the set of one-dimensional representations of a \(G\)-algebra \(A\), and prove, moreover, that if the set of finite dimensional representations of \(A\) over a ground field \(K\) is not empty, then the homological dimension of \(A\) equals \(n\). All the algorithms are implemented in a kernel extension Plural of the computer algebra system Singular. We discuss the efficiency of computations and provide a comparison with other computer algebra systems. We propose a collection of benchmarks for testing the performance of algorithms; the comparison of timings shows that our implementation outperforms all of the modern systems with the combination of both broad functionality and fast implementation. In the thesis, there are many new non-trivial examples, and also the solutions to various problems, arising in different fields of mathematics. All of them were obtained with the developed theory and the implementation in Plural, most of them are treated computationally in this thesis for the first time.
  • Nichtkommutative Polynomalgebren entstehen in vielen verschiedenen Anwendungen, von Quantengruppen und Theoretischer Physik bis zu linearen Differentiellen und Differenzengleichungen. In der Arbeit wurde ein Rahmen entwickelt, in dem viele wichtige Algebren der Klassen \(G\)- und \(GR\)-Algebren zusammengeführt und ihre ringtheoretischen Eigenschaften untersucht wurden. Sei \(A\) eine \(G\)-Algebra mit \(n\) Variablen. Es werden notwendige und hinreichende Bedingungen dafür angegeben, daß \(A\) eine Poincar'e-Birkhoff-Witt (PBW) Basis besitzt. Es wird gezeigt, dass \(A\) neben der Existenz einer PBW Basis, weitere Eigenschaften mit dem kommutativen Polynomring \(\mathbb{K}[x_1,\ldots,x_n]\) gemeinsam hat. \(A\) ist ein Noetherscher Integritätsbereich der Gel'fand-Kirillov-Dimension \(n\). Die Krull- und die globale homologische Dimension von \(A\) sind durch \(n\) beschränkt ; es werden Beispiele von \(G\)-Algebren gegeben, bei denen diese Ungleichheiten strikt sind. Schließlich wurde bewiesen, dass \(A\) eine Auslander-reguläre und eine Cohen-Macaulay Algebra ist. Für symbolische Berechnungen mit Moduln über \(GR\)-Algebren, wurde die Gröbnerbasentheorie verallgemeinert, neue und bestehende Algorithmen werden entwickelt und verbessert. Wir verbinden die grundlegendsten Algorithmen mit einer Reihe von Anwendungen, welche man in der Literatur als "Gröbner basics" bezeichnet. Weiterhin wurden Algorithmen diskutiert, die nur im nichtkommutativen Fall existieren, darunter zweiseitige Gröbnerbasen für Bimoduln, Annihilatoren von Linksmoduln und Operationen mit entgegengesetzten Algebren. Eine wichtige Rolle in der Darstellungstheorie spielen die verschiedenen Unteralgebren, wie z.B. das Zentrum und die Gel'fand-Zetlin Unteralgebra. Die Eigenschaften und ihre Beziehungen zu Gröbnerbasen wurden untersucht und einige Aspekte ihrer Berechnung diskutiert. Im Kapitel über algorithmische Studien von Morphismen zwischen \(GR\)-Algebren wurde die Untersuchung zu diesen Unteralgebren fortgesetzt. Es wurden neue Ergebnisse and Algorithmen zur Berechnung des Urbilds eines Linksideals unter einem Morphismus von \(GR\)-Algebren erzielt. Die Ergebnisse und Begrenzungen verschiedener Methoden, die vorgeschlagen wurden, wurden gezeigt. Diese Technik wurde auch für die Berechnung des Kerns eines Morphismus, die Zerlegung eines Moduls in zentrale Charaktere und die algebraische Abhängigkeit von paarweise kommutierenden Elementen verwendet. Es wurde ein Algorithmus für die Berechnung von eindimensionalen Darstellungen einer \(G\)-Algebra \(A\) erstellt. Es wurde bewiesen, dass die homologische Dimension von \(A\) über einem Körper \(K\) gleich der Anzahl der Variablen von \(A\) ist, falls es endlich-dimensionale Darstellungen von \(A\) existieren. Alle Algorithmen wurden in eine Kern-Erweiterung Plural des Computeralgebrasystem Singular implementiert. Die Effizienz der Berechnungen wurde diskutiert und ein Vergleich mit anderen Computeralgebrasystemen erstellt. Es wurde eine Reihe von Benchmarks zum Test der Leistung von Algorithmen vorgeschlagen. Der Zeitvergleich zeigt, dass unsere Implementierung alle modernen Systeme hinsichtlich der Kombination von Funktionalität und Geschwindigkeit übertrifft. In der Arbeit gibt es eine Vielzahl von nichttrivialen Beispielen und Lösungen zu verschiedenen Problemen aus verschiedensten Bereichen der Mathematik. All wurden mit Hilfe der entwickelten Theorie und der Implementation in Plural erzielt, die meisten von ihnen wurden in dieser Arbeit zum ersten Mal berechnet.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Viktor Levandovskyy
URN (permanent link):urn:nbn:de:hbz:386-kluedo-18830
Advisor:Gert-Martin Greuel
Document Type:Doctoral Thesis
Language of publication:English
Year of Completion:2005
Year of Publication:2005
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2005/06/08
Tag:Algebraische Abhängigkeit der kommutierende Elementen; Computeralgebra System; Das Urbild von Ideal unter einen Morphismus der Algebren
Algebraic dependence of commuting elements; Computer Algebra System; Preimage of an ideal under a morphism of algebras
GND-Keyword:Computeralgebra ; Eliminationsverfahren ; Gröbner-Basis; Morphismus; Nichtkommutative Algebra
Faculties / Organisational entities:Fachbereich Mathematik
DDC-Cassification:510 Mathematik
MSC-Classification (mathematics):13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
16E10 Homological dimension
16S30 Universal enveloping algebras of Lie algebras [See mainly 17B35]
16W70 Filtered rings; filtrational and graded techniques
16Z05 Computational aspects of associative rings [See also 68W30]
68W30 Symbolic computation and algebraic computation [See also 11Yxx, 12Y05, 13Pxx, 14Qxx, 16Z05, 17-08, 33F10]

$Rev: 12793 $