The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 65 of 81
Back to Result List

Gröbner Bases over Extention Fields of \(\mathbb{Q}\)

  • Gröbner bases are one of the most powerful tools in computer algebra and commutative algebra, with applications in algebraic geometry and singularity theory. From the theoretical point of view, these bases can be computed over any field using Buchberger's algorithm. In practice, however, the computational efficiency depends on the arithmetic of the coefficient field. In this thesis, we consider Gröbner bases computations over two types of coefficient fields. First, consider a simple extension \(K=\mathbb{Q}(\alpha)\) of \(\mathbb{Q}\), where \(\alpha\) is an algebraic number, and let \(f\in \mathbb{Q}[t]\) be the minimal polynomial of \(\alpha\). Second, let \(K'\) be the algebraic function field over \(\mathbb{Q}\) with transcendental parameters \(t_1,\ldots,t_m\), that is, \(K' = \mathbb{Q}(t_1,\ldots,t_m)\). In particular, we present efficient algorithms for computing Gröbner bases over \(K\) and \(K'\). Moreover, we present an efficient method for computing syzygy modules over \(K\). To compute Gröbner bases over \(K\), starting from the ideas of Noro [35], we proceed by joining \(f\) to the ideal to be considered, adding \(t\) as an extra variable. But instead of avoiding superfluous S-pair reductions by inverting algebraic numbers, we achieve the same goal by applying modular methods as in [2,4,27], that is, by inferring information in characteristic zero from information in characteristic \(p > 0\). For suitable primes \(p\), the minimal polynomial \(f\) is reducible over \(\mathbb{F}_p\). This allows us to apply modular methods once again, on a second level, with respect to the modular factors of \(f\). The algorithm thus resembles a divide and conquer strategy and is in particular easily parallelizable. Moreover, using a similar approach, we present an algorithm for computing syzygy modules over \(K\). On the other hand, to compute Gröbner bases over \(K'\), our new algorithm first specializes the parameters \(t_1,\ldots,t_m\) to reduce the problem from \(K'[x_1,\ldots,x_n]\) to \(\mathbb{Q}[x_1,\ldots,x_n]\). The algorithm then computes a set of Gröbner bases of specialized ideals. From this set of Gröbner bases with coefficients in \(\mathbb{Q}\), it obtains a Gröbner basis of the input ideal using sparse multivariate rational interpolation. At current state, these algorithms are probabilistic in the sense that, as for other modular Gröbner basis computations, an effective final verification test is only known for homogeneous ideals or for local monomial orderings. The presented timings show that for most examples, our algorithms, which have been implemented in SINGULAR [17], are considerably faster than other known methods.
  • Gröbnerbasen sind eines der leistungsfähigsten Werkzeuge in der Computeralgebra und der kommutativen Algebra, mit Anwendungen in algebraischer Geometrie und Singularitätentheorie. Aus theoretischer Sicht können solche Basen mit dem Algorithmus von Buchberger über beliebigen Körpern berechnet werden. In der Praxis hängt die Effizienz solcher Berechnungen aber von der Arithmetik im Koeffizientenkörper ab. In dieser Dissertation betrachten wir Berechnungen von Gröbnerbasen über zwei verschiedenen Arten von Koeffizientenkörpern. Im ersten Fall betrachten wir einfache Erweiterungen \(K = \mathbb{Q}(\alpha)\), wobei \(\alpha\) eine algebraische Zahl sei und wir das Minimalpolynom von \(\alpha\) mit \(f \in \mathbb{Q}[t]\) bezeichnen. Im zweiten Fall sei \(K'\) der algebraische Funktionenkörper über \(\mathbb{Q} \) mit transzendenten Parametern \(t_1, \ldots, t_m\), also \(K' = \mathbb{Q}(t_1, \ldots, t_m)\). Insbesondere stellen wir effiziente Algorithmen zur Berechnung von Gröbnerbasen über \(K\) und \(K'\) vor. Au\ss{}erdem stellen wir eine effiziente Methode zur Berechnung von Syzygienmoduln über \(K\) vor. Um Gröbnerbasen über \(K\) zu berechnen, fügen wir, ausgehend von den Ideen von Noro [35], das Polynom \(f\) zum betrachteten Ideal hinzu, mit \(t\) als zusätzlicher Variable. Anstatt aber überflüssige Reduktionen von S-Paaren durch das Invertieren algebraischer Zahlen zu vermeiden, erreichen wir dasselbe Ziel durch Anwendung modularer Methoden wie in [2,4,27], also durch Rückschlüsse von Daten in Charakteristik \(p> 0\) auf Daten in Charakteristik Null. Für geeignete Primzahlen \(p\) ist das Minimalpolynom \(f\) über \(\mathbb{F}_p\) reduzibel. Dies erlaubt uns,auf einer zweiten Ebeneein weiteres Mal modulare Methoden anzuwenden, bezüglich der modularen Faktoren von \(f\). Der Algorithmus gleicht daher einer Teile-und-herrsche-Strategie und ist insbesondere leicht zu parallelisieren. Außerdem stellen wir einen Algorithmus zur Berechnung von Syzygienmoduln über \(K\) vor, der einen ähnlichen Ansatz verfolgt. Um hingegen Gröbnerbasen über \(K'\) auszurechnen, werden in dem neuen Algorithmus zunächst verschiedene konkrete Werte für die Parameter \(t_1, \ldots, t_m\) eingesetzt, um das Problem von \(K'[x_1, \ldots, x_n]\) auf \([x_1, \ldots, x_n]\) zurückzuführen. Der Algorithmus berechnet dann eine Menge von Gröbnerbasen der so erhaltenen Ideale. Aus dieser Menge von Gröbnerbasen mit Koeffizienten in \(\mathbb{Q}\) wird dann durch Sparse Multivariate Rational Interpolation eine Gröbnerbasis des Inputideals berechnet. Dem gegenwärtigen Stand nach sind diese Algorithmen probabilistisch in dem Sinne, dass wie bei anderen modularen Gröbnerbasisberechnungen ein effektiver finaler Verifikationstest nur für homogene Ideale oder für lokale Monomordnungen bekannt ist. Die vorgelegten Laufzeitmessungen zeigen, dass die neuen, in SINGULAR [17] implementierten Algorithmen bei den meisten Beispielen wesentlich schneller sind als andere bekannte Methoden.

Download full text files

Export metadata

Metadaten
Author:Dereje Kifle Boku
URN:urn:nbn:de:hbz:386-kluedo-44289
Advisor:Wolfram Decker
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2016/08/10
Year of first Publication:2016
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2016/08/05
Date of the Publication (Server):2016/08/10
Tag:Gröbner bases; algebraic function fields; algebraic number fields; dense univariate rational interpolation; sparse interpolation of multivariate rational functions; sparse multivariate polynomial interpolation; syzygies
Page Number:xi, 150
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):13-XX COMMUTATIVE RINGS AND ALGEBRAS / 13Pxx Computational aspects and applications [See also 14Qxx, 68W30]
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015