Stabile numerische Berechnung von Gröbner-Basen

Polynome in mehreren Veränderlichen spielen eine wichtige Rolle in vielen Anwendungsgebieten (z.B. computerunterstütztes Entwerfen, Robotik, Chemieingenieurwesen usw.). Gröbner-Basen stellen das zentrale Werkzeug für die Lösung algorithmischer Probleme bei Systemen multivariater Polynome dar, insbesondere für die Berechnung der Nullstellen solcher Systeme. Gängige Computer-Algebra-Systeme enthalten Codes für die Berechnung von Gröbner-Basen für spezifizierte Systeme; diese Codes müssen aber wegen ihrer potentiellen numerischen Instabilität in rationaler Arithmetik ausgeführt werden, was ihre Laufzeit unnötig verlängert. Diese Instabilität rührt von wesentlichen Unstetigkeiten in den klassischen Gröbner-Basen her, was ihre Benützung für Probleme mit Daten beschränkter Genauigkeit verhindert, wie sie in Anwendungen standardmäßig auftreten. Der Antragsteller hat kürzlich den Begriff der Gröbner-Basen so verallgemeinert, daß eine lokale Eliminierung dieser Unstetigkeiten möglich wird. Das eröffnet die Möglichkeit zum Entwurf von numerisch stabilen Algorithmen zur Berechnung von erweiterten Gröbner-Basen, die algorithmisch genauso wie klassische Gröbner- Basen eingesetzt werden können, z.B. für die Nullstellenberechnung. Das Ziel des beantragten Projekts ist der komplette Entwurf und eine Implementierung eines Algorithmus für die folgende Aufgabenstellung: Gegeben seien n Polynome in s Variablen, mit Koeffizienten, die eine (spezifizierte) beschränkte Genauigkeit haben können; man berechne eine Näherung für die erweiterte Gröbner-Basis dieser Polynome, für eine gegebene Termordnung. Der Algorithmus muß die Ausführung in Gleitpunkt-Arithmetik ohne Gefahr einer Instabilität gestatten. Die Genauigkeit der berechneten Näherung muß der Genauigkeit der Eingabedaten entsprechen. Der Entwurf des Algorithmus wird sich auf den Umstand stützen, daß die möglichen Unstetigkeiten von Gröbner- Basen durch das Erzwingen einer eindeutigen Beziehung zwischen polynomialen Idealen und Normalsets entstehen. Wenn man eine größere Auswahl von Normalsets zuläßt, dann kann man den Normalset in einer vollen Umgebung des gegebenen Polynomsystems invariant halten. Dies führt dann zu einer erweiterten Gröbner-Basis, die in dieser Umgebung stetig ist. Rechnerisch zeigt sich die Nähe einer Unstetigkeit durch das Auftreten von führenden Termen mit sehr kleinen Koeffizienten in den unterwegs auftretenden Polynomen. Ein stabilisierter Algorithmus muß dann einen vom Standard-Algorithmus abweichenden Weg einschlagen. Die Details dieses neuen algorithmischen Entwurfs und Beweise für seine Gültigkeit werden die zentrale Aufgabe des Projekts sein.

Es wurde ein Algorithmus entwickelt und implementiert, der die numerische Berechnung der erweiterten Groebner- Basis eines regulären Systems polynomialer Gleichungen in Gleitpunkt-Arithmetik gestattet. Polynome in mehreren Veränderlichen sind wichtige Modelle in vielen Anwendungsgebieten (z.B. computergestütztes Entwerfen, Computer-Vision, Robotik, Chemieingenieurwesen etc.). Groebner-Basen sind das zentrale Werkzeug bei der Computer-Simulation vieler einschlägiger Probleme, insbesondere für die Berechnung von Nullstellen. Derzeitige Codes für die Berechnung von Groebner-Basen verwenden die langsame rationale Arithmetik und liefern möglicherweise Ergebnisse, die nicht geeignet zur Weiterverarbeitung sind. Der im Projekt entwickelte Algorithmus vermeidet nahezu ausgeartete Situationen so weit wie möglich, er kann deshalb in schneller Gleitpunkt-Arithmetik durchgeführt werden. Weiters liefert er auch dann sinnvolle Ergebnisse, wenn die Problemdaten von beschränkter Genauigkeit sind. Er kann deshalb zur rechnerischen Analyse von verschiedensten nichtlinearen Modellen bei realistischen technisch-wissenschaftlichen Problemstellungen eingesetzt werden.