Fachgruppentagung Kassel 2009 – Hauptvorträge

Claus Diem (Universität Leipzig): Komplexität grundlegender algorithmischer Fragestellungen der Computeralgebra

In der Computeralgebra liest man oftmals Aussagen wie die folgende: “Zwei Polynome von Grad kleiner-gleich n können mit O(n log(n) log log(n)) Körperoperationen multipliziert werden.” Während Aussagen wie diese eine offensichtliche intuitive Bedeutung haben, sind mathematisch präzise Interpretationen nicht so offensichtlich. In der Tat gelangt man mit den üblichen Definitionen der theoretischen Informatik zu mehr Fragen als Antworten. Was ist das zugrundeliegende Modell? Ist es eine Turingmaschine oder ein RAM-Modell? Wie werden die Körperelemente dargestellt? Gibt es nicht noch einen “Overhead”, der sich nicht in Körperoperationen ausdrücken lässt, aber trotzdem berücksichtigt werden sollte?

In diesem Übersichtsvortrag werden verschiedene Rechenmodelle vorgestellt und die Komplexität einiger grundlegener Probleme der theoretischen Informatik und der Computeralgebra in diesen Modellen untersucht.

Almar Kaid (Universität Osnabrück): Semistabile Vektorbündel und Computeralgebra

Semistabile Vektorbündel und deren Modulräume spielen eine zentrale Rolle in der algebraischen Geometrie. Durch eine bahnbrechende Arbeit von A. Langer aus dem Jahr 2004 ist derzeit insbesondere der Fall von Bündeln auf Varietäten in positiver Charakteristik ein beliebter Forschungsgegenstand. In positiver Charakteristik ergibt sich durch den Frobenius-Morphismus der Begriff der starken Semistabilität. Wir geben einen Überblick über algorithmische Methoden, die es erlauben, die Semistabilität bzw. starke Semistabilität eines gegebenen Vektorbündels zu testen. Weiter untersuchen wir gewisse Syzygienbündel auf Fermat-Kurven auf deren Stabilitätsverhalten. Hier erweist sich die Computeralgebra als äußerst hilfreich. Überdies ergeben sich mit den aufgezeigten Bündelmethoden Algorithmen zur Berechnung der Hilbert-Kunz-Funktion und des straffen Abschlusses gewisser Ideale in einem zwei-dimensionalen Fermat-Hyperflächenring.

Viktor Levandovskyy (RWTH Aachen): Constructive D-Module Theory

Let R be a commutative ring K[x1,…,xn] over a field K=C, and D=D(R) be the n-th Weyl algebra, that is the associative K-algebra generated by {x1,…,xn,∂1,…,∂n} subject to relations jxi=xijij for all 1≤i,j≤n. A short overview of the properties of Weyl algebras and a sketch on Gröbner bases theory for them will be given. Indeed, Weyl algebra is the algebra of linear partial differential operators with polynomial coefficients.

How to compute a (possibly smallest) system of PDE’s with polynomial coefficients, such that f in R is a solution of such system? Since R is a finitely presented D(R)-module with the natural action xi•p=xi⋅p, ∂i•p=∂p/∂xi, we get the answer by computing (using Gröbner bases) a left ideal AnnD(R)f={a in D(R) | a•f=0}.

We can compute the annihilator of fα for any special α in C as before. D-module theory allows us to compute the annihilator of fs for symbolic s and, moreover, s appears in the annihilator AnnD(R)[[s]fsD(R)[[s]=D(R)K[[s] polynomially!

As an application, an algorithm to compute the D(R)-module structure of the localization K[[x]F for F={fi | i≥0}⊆R explicitly will be demonstrated.

J. Bernstein proved in 1972, that for a polynomial f in R there exist an operator P(s) in D(R)[[s] and a monic polynomial b(s) in K[[s], such that for any s holds the equality Pf(s) • fs+1 = bf(s) ⋅ fs. bf(s) is called the Bernstein-Sato polynomial of f. The famous theorem of Kashiwara states, that all roots of bf(s) are rational numbers. The integer roots of Bernstein-Sato polynomial are of big importance in many applications. We show, that if the hypersurface, defined by f, is smooth, then bf(s)=s+1. Otherwise bf(s) might be very nontrivial and its computation very challenging. We show, how to compute bf(s) and Pf(s) effectively. Some important applications of D-modules, such as symbolic integration, will be discussed and accompanied by nontrivial live examples, computed with the Singular:Plural package for D-modules.

Thomas Markwig (Technische Universität Kaiserslautern): Methoden der Computeralgebra in der tropischen Geometrie

Die tropische Geometrie ist ein recht junges Teilgebiet der algebraischen Geometrie. Im Prozess der Tropikalisierung werden die Lösungsmengen algebraischer Gleichungen durch stückweise lineare Objekte ersetzt, die den Einsatz neuer Methoden (etwa aus dem Bereich der diskreten Mathematik) in der algebraischen Geometrie erlauben. Insbesondere im Bereich der enumerativen Geometrie hat es in den vergangenen Jahren einige bahnbrechende Ergebnisse in diese Richtung gegeben. Ein wesentlicher Grundgedanke ist dabei, daß die stückweise linearen Objekte leichter zu handhaben sind als die nicht-linearen Ausgangsobjekte. Für viele theoretische Fragen ist dies korrekt. Wenn es aber darum geht, zu gegebenem Ideal die tropische Varietät zu berechnen, so ist das vom Rechneraufwand her sehr komplex. Es müssen in aller Regel sehr viele Gröbnerbasisberechnungen durchgeführt werden. Wir wollen in unserem Vortrag die grundlegenden Begriffe einführen und einige Algorithmen aus dem Bereich der tropischen Geometrie vorstellen.

Thomas Sturm (Universität Passau, Universidad de Cantabria Santander): Algorithmische Quantorenelimination

Das Logikpaket REDLOG des Computeralgebrasystems REDUCE erweitert die Idee des symbolischen Rechnens von algebraischen Ausdrücken auf Formeln erster Stufe über fixierten algebraischen Bereichen. Diese umfassen derzeit komplexe Zahlen, reelle Zahlen, die lineare Theorie der ganzen Zahlen und der p-adischen Zahlen, Warteschlangen über reellen Zahlen, Differentialalgebren, Termalgebren vom Malcev-Typ und quantifizierten Aussagenkalkül. Im Gegensatz zu klassischen Theorembeweisern ist durch die Fixierung des Domains die gesamten Palette der klassischen Computeralgebra in diesem Rahmen anwendbar. Umgekehrt ergeben sich natürliche Anwendungen der Computerlogik bei parametrischen Varianten klassischer algebraischer Probleme, wie etwa umfassenden Gröbnerbasen. Darüber zieht REDLOG zahlreiche Anwender aus anderen Gebieten der Mathematik, Informatik, Physik und Biologie an. Der Vortrag gibt einen Überblick über die existierenden Domains in Verbindung mit einer kurzen Einführung in das zentrale Konzept der effektiven Quantorenelimination. Wir stellen die REDLOG-Webseite vor, die unter anderem eine Online-Datenbank mit Literatur und Rechenbeispielen zur Verfügung stellt. Schließlich diskutieren wir laufende REDLOG-Projekte und zukünftig geplante Entwicklungen.