Jedenfalls hat mich Loos darauf hingestoßen, dass die Dinge, mit denen ich mich in der Dissertation beschäftigt hatte, jetzt von größtem Interesse für die Entwicklung einer neuen Generation mathematischer Softwaresysteme wären, und zwar eben für Probleme, für die man damals keine Methoden hatte. Und das hat mich gewaltig motiviert, mich in der Forschung wieder mit vollem Fokus auf das Gebiet der Gröbner-Basen zu stürzen, das ich seinerzeit aus Frust über die Nichtbeachtung durch Gröbner verlassen hatte. Als Resultat habe ich kurz darauf eine wesentliche Verbesserung meines Algorithmus gefunden und diese 1979 publiziert, ohne die auch mit heutigen Rechnern nur kleine Beispiele in vernünftiger Rechenzeit gelöst werden könnten.
Ich habe mich dann auch intensiv in die damals noch kleine internationale Community eingebracht, die das Gebiet der „Computer-Algebra“ und der darauf aufbauenden mathematischen Softwaresysteme hochgezogen hat. Loos verdanke ich auch die Bekanntschaft mit George E. Collins, dessen Methode der „cylindrical algebraic decompositions“ (1975 erstmalig in völliger Allgemeinheit publiziert) einen revolutionären Beitrag zur Computer-Algebra darstellt, deren Bedeutung nicht überschätzt werden kann. Leider kann ich seine Leistung und die Grundgedanken seiner Methode in diesem Rahmen nicht wirklich erklären. Wir haben uns jedenfalls 1982 zusammengetan, um das erste Sammelwerk über das junge Gebiet der Computer-Algebra zu schreiben, was dem Gebiet, wie ich hoffe, einen wesentlichen Impuls gegeben hat.11
Ein interessantes mathematisches Problem, das Sie in Ihrer Dissertation gelöst haben, und ein interessanter Grund, warum die Gröbner-Basen den Namen von Gröbner haben: Aber was sind nun die Gröbner-Basen?
Die Theorie der Gröbner-Basen ist eine mathematische Theorie, mit welcher es möglich ist, beliebige sogenannte nicht lineare, algebraische Gleichungssysteme zu behandeln. Der abstrakte Raum, in welchem sich diese Theorie abspielt, ist der Raum der sogenannten „Polynomideale“.
Nicht lineare Gleichungssysteme kommen faktisch überall in den Naturwissenschaften, in der Technik, Medizin, Wirtschaft vor. Einige Beispiele von Problemen aus Naturwissenschaft und Technik, die durch Polynomideale beschrieben werden können, habe ich in einer der vorigen Fragen gegeben (vgl. Seite 16).
Die „Nicht-Linearität“ macht hier die Schwierigkeit aus. Eine Tischoberfläche ist etwas „Lineares“, ein Bilderrahmen ist (meist) etwas Lineares. Wenn man einen Bilderrahmen auf einen Tisch stellt, entsteht eine Kante, wo sich Tisch und Bild schneiden. Die ist „linear“. Wenn hingegen ein Ball (etwas „Nicht-Lineares“) in eine spiegelglatte („lineare“) Wasseroberfläche eintaucht, ist die Schnittlinie etwas „Nicht-Lineares“, nämlich ein Kreis. Eine Tischoberfläche ist „zweidimensional“, die Bilderrahmenkante ist „eindimensional“, die Balloberfläche ist „zweidimensional“, der Ball selbst mitsamt seinem Inhalt ist „dreidimensional“. In der Technik, Wirtschaft, Biologie etc. kommen (gedankliche) Gebilde vor, die viele Dimensionen (auch „Freiheitsgrade“/„unabhängige Variable“/„Parameter“ genannt) haben.
Zum Beispiel hat ein Roboterarm mit drei Gelenken und einem Greifer, der sich in jede Richtung orientieren kann (und dazu weitere drei Gelenke braucht), sechs voneinander unabhängige Möglichkeiten, die Position zu beeinflussen. Er hat also sechs „Freiheitsgrade“, bewegt sich also in einem „sechsdimensionalen“ Raum. Die Abhängigkeit der Position des Greifers von den Gelenkstellungen ist nicht linear. Wenn sich zwei Roboter in einem Arbeitsraum so bewegen sollen, dass sie nicht zusammenstoßen, geht es darum, die Schnittmenge zweier sechsdimensionaler nicht linearer Gebilde zu analysieren, um zum Beispiel herauszufinden, wo durch Kollision der Arme etwas passieren könnte.
Es ist sehr schwierig, Probleme mit nicht linearen Gebilden mathematisch zu behandeln. Deshalb behilft man sich meist dadurch, dass man die nicht linearen Gebilde durch viele kleine lineare approximiert, zum Beispiel eine Kugel durch lauter kleine Dreiecke an der Oberfläche. Dann werden alle Probleme linear und bei diesen (auch mit sehr vielen Dimensionen) weiß man seit Langem, wie man sie effizient lösen kann. Leider entstehen durch das Ersetzen von nicht linearen Gebilden durch lineare Gebilde Fehler, die sich aufschaukeln und zu gefährlichen Fehlschlüssen, falschen Vorhersagen, fehlerhaften Konstruktionen, Abtriften in gefährliche Bereiche etc. führen können. Man wusste seit 1899 durch die Arbeiten des deutschen Mathematikers Paul Gordan, dass sich faktisch alle wichtigen Probleme für nicht lineare Gebilde und Systeme solcher Gebilde einheitlich lösen ließen, wenn man alle solchen Gebilde in eine gewisse „Standardform“ überführen könnte, bei der die einzelnen Variablen in einem gewissen Sinne entkoppelt sind. Genau das leisten die Gröbner-Basen!
Anmerkungen
Wolfgang Gröbner (1899 – 1980), ordentlicher Professor für Mathematik an der Universität Innsbruck, wurde vor allem durch seine Arbeiten über die sogenannten Lie-Reihen zur Lösung von Differenzialgleichungen und über die Theorie der sogenannten Polynomideale bekannt. Sehr berühmt war auch seine Integraltafel (mit Nikolaus Hofreiter).
Das Problem wurde 1899 in einer etwas anderen Form vom deutschen Mathematiker Paul Gordan (1837 – 1912) gestellt.
Man sagte „die ZUSE“, abgeleitet von „die Rechenmaschine“ ZUSE; nicht „der“ Computer ZUSE. „Der“ Zuse war der Erfinder, nämlich der deutsche Ingenieur Konrad Zuse, in dessen Firma in Bad Hersfeld ich 1964 auch eine fünfmonatige Hardwareschulung für „die“ ZUSE erhielt.
Rigorosum: die letzte, umfassende, „strenge“ Prüfung beim Doktoratsstudium.
2013 hat Peter Paule dazu das Buch „Mathematics, Computer Science and Logic – A Never Ending Story“ (Springer, Heidelberg) herausgegeben. Es umfasst Gedanken namhafter Mathematiker über das Zusammenspiel dieser drei Gebiete.
Algorithmus: eine durch den Computer ausführbare Methode zur Lösung eines mathematischen Problems.
Hans Knapp (später Professor an der Johannes Kepler Universität Linz; leider 2004 allzu früh verstorben) und Gerhard Wanner (später viele Jahre Professor an der Universität Genf und ein sehr bedeutender numerischer Mathematiker).
Der Titel meines Vortrags war „Machine-independent Complexity Theory“. Natürlich hängt die Komplexität von Berechnungen wesentlich vom verwendeten Computer ab. Der Titel war also provokant, denn in der Tat kann man sehr viele fundamentale Dinge über Komplexität relativ zur Hardwaregeschwindigkeit der konkreten Maschine sagen. Die feine Provokation, die zum Denken anregen sollte, hatte also voll eingeschlagen, allerdings zu meinem Schaden.
Yuri Matiyasevich hat 1970 gezeigt, dass das berühmte „Zehnte Hilbert-Problem“, das