Forschungsbericht 2021 - Max-Planck-Institut für Mathematik in den Naturwissenschaften

Lösen von polynomiellen Gleichungen

Autoren
Breiding, Paul
Abteilungen
Emmy-Noether-Forschungsgruppe "Numerical and Probabilistic Nonlinear Algebra"
Zusammenfassung
Viele praktische Probleme lassen sich auf das Lösen von polynomiellen Gleichungssystemen zurückführen. In diesem Bericht wird eine solche Anwendung vorgestellt. Ausgehend von diesem Beispiel wird diskutiert, was grundlegende Strategien sind um Lösungen zu berechnen und was es in diesem Kontext eigentlich konkret heißt, ein Gleichungssystem zu lösen. Dabei soll herausgearbeitet werden, dass anwendungsbezogene und theoretische Fragestellungen sich nicht gegenseitig ausschließen, sondern einander ergänzen.

Polynomielle Gleichungen sind Gleichungen mit möglicherweise mehreren Unbekannten, in denen sich beide Seiten als Summe von Vielfachen von endlichen Produkten dieser Unbekannten schreiben lassen. So ist beispielsweise p(x1,x2)=x12-x1+x2+x1∙x2=0 eine polynomielle Gleichung, aber 2x=0 ist keine, da sich die Funktion 2x nicht als Summe von endlich vielen Produkten von x darstellen lässt. Ein System polynomieller Gleichungen ist ein Gleichungssystem der Form

p1(x)=…=pn(x)=0,

wobei p1, …, pn allesamt Polynome in n Variablen x=(x1,…,xn) sind. Das Problem dieses Gleichungssystem zu lösen, ist, Werte z1,…, zn zu finden, so dass die n Polynome Null ergeben, wenn man sie an diesen Werten auswertet. Die Menge aller solcher Werte wird eine algebraische Varietät genannt.

Maschinelles Sehen, Algebra und Dinosaurier

In dieser Form klingt das Problem sehr theoretisch. Warum soll die Lösung überhaupt von Interesse sein? Hier ist ein Beispiel. Ein beliebtes Modell im maschinellen Sehen ist das sogenannte Pinhole-Camera-Model. Dieses Modell ist eine mathematische Abstraktion einer gewöhnlichen Lochkamera, welche einen sogenannten Weltpunkt x=(x1,x2,x3) in ein zweidimensionales Foto y=(y1,y2) überführt. Der Mechanismus des Fotografierens wird dabei durch eine rationale Funktion modelliert: y1=p1(x)/q1(x) und y2=p2(x)/q2(x), wobei p1, p2, q1 und q2 Polynome sind. In anderen Worten, q1(x)∙y1 - p1(x) = q2(x)∙y2-p2(x)=0 ist ein System polynomieller Gleichungen in x und für jede Kamera ergibt sich ein solches Kamera-Gleichungssystem.

Das Problem der Triangulierung im maschinellen Sehen besteht darin, für eine Reihe von Fotos von verschiedenen Kameras den zugehörigen Weltpunkt zu berechnen. Der Einfachheit halber soll das Problem jetzt für zwei Kameras betrachtet werden. Gegeben sind dann zwei Fotos u=(u1,u2) und v=(v1,v2). Da davon auszugehen ist, dass die Daten mit Messfehlern versehen sind, wird die Triangulierung als ein Problem kleinster Quadrate modelliert. Um den Weltpunkt zu berechnen, wird folgendes Minimierungsproblem gelöst:

min (u1 - y1)2 + (u2 - y2)2 + (v1 - z1)2 + (v2 - z2)2

unter den Bedinungen, dass y das Kamera-Gleichungssystem der ersten Kamera erfüllt und z das der zweiten Kamera. Das Verfahren der Lagrange-Multiplikatoren zur Lösung dieses Optimierungsproblems erfordert es dann, die Nullstellen eines Systems polynomieller Gleichungen zu berechnen. Abbildung 1 zeigt das Ergebnis der Berechnung von 4983 Weltpunkten [1, 2]. Welches Objekt verbirgt sich wohl dahinter?

Ein numerisches Verfahren zum Lösen polynomieller Gleichungen

Es ist für die konkrete Anwendung nicht immer wichtig die exakten Werte der Lösungen zu kennen. Tatsächlich ist das auch gar nicht immer möglich. Es reicht oft hingegen, numerische Approximationen der Lösungen zu berechnen. Das heißt, es werden Werte x1,…,xn berechnet, die nah an den exakten Lösungswerten liegen. In unserer Forschungsgruppe implementieren [3] und studieren wir ein bestimmtes numerisches Verfahren zum Lösen von polynomiellen Gleichungen — das sogenannte Homotopie-Verfahren.

Das Homotopie-Verfahren zum Lösen von polynomiellen Gleichungen funktioniert wie folgt. Der Einfachheit halber wird ab jetzt das zu lösende Gleichungssystem mit p(x)=0 bezeichnet. Um dies zu Lösen wird ein sogenanntes Start-System q(x) und dessen Nullstellen berechnet. Dann werden p(x) und q(x) mit einer “Strecke” verbunden. Das kann man sich wie die blaue Strecke in der Ebene Q in Abbildung 2 vorstellen, nur dass die Strecke in einem Raum von sehr großer Dimension liegt, in dem p(x) und q(x) selbst Punkte sind. Die blaue Strecke induziert grüne Pfade zwischen den Nullstellen von p(x) und q(x) und die Nullstellen werden mithilfe des Newton-Verfahrens Schritt für Schritt entlang dieser grünen Pfade transportiert.

Aber damit wurde das Problem nur verschoben — wie löst man q(x)=0? Indem man q(x) so gestaltet, dass es möglich ist! Zum Beispiel könnte man q(x)=(x1d1 - 1, … , xndn - 1) =0 wählen, wobei d1 der Grad von p1(x) ist und so weiter. Der Grad eines Polynoms ist der maximale Wert der Exponentensumme jedes Terms. Beispielsweise hat das Polynom x1∙x2+x1 zwei Terme mit Exponentensummen 2 und 1, also Grad 2. Dadurch, dass in q(x) die Variablen entkoppelt sind, lässt es sich leicht lösen und für Homotopie-Verfahren verwenden. Lösen heißt hier allerdings Lösen über den komplexen Zahlen — zum Beispiel hat das Polynom x13-1 zwei komplexe und nicht-reelle Lösungen. In den Anwendungen sind meist nur die reellen Werte interpretierbar, aber es ist (außer in sehr speziellen Situationen) nicht möglich vorherzusagen, wie viele reelle Lösungen ein System hat. Demzufolge ist es notwendig alle komplexen Lösungen zu berechnen und die reellen auszuwählen.

Abstrakte Geometrie und anwendungsbezogene Methoden ergänzen einander

Das obige Start-System hat eine sehr simple Struktur. Diese Einfachheit hat allerdings auch ihre Nachteile: Die Anzahl der Lösungen von q(x)=0 explodiert förmlich, sobald die Grade auch nur moderat steigen. Für konkrete Rechnungen bedeutet das, dass viele Lösungen des Start-Systems q(x) eventuell umsonst transportiert werden, weil die Anzahl der Lösungen von p(x)=0 viel kleiner ist als die Anzahl der Lösungen von q(x)=0. Um die Effektivität des Homotopie-Verfahrens zu verbessern, ist es von zentraler Bedeutung, bessere Startsysteme zu finden. Hierfür sind Methoden aus der abstrakten algebraischen Geometrie essentiell und unabdingbar.

Es gibt also einen direkten Zusammenhang zwischen anwendungsbezogenen Problemen wie der Triangulierung im maschinellen Sehen und theoretische Fragen in Geometrie und Algebra. Es ist eines unserer Hauptziele am Max-Planck-Institut für Mathematik in den Naturwissenschaften diesen Zusammenhang besser zu verstehen und nutzbar zu machen. Anwendungsbezogene und theoretische Fragestellungen schließen sich nicht aus, sondern ergänzen einander.

Fußnoten

[1]: Die verwendete Datenmenge ist frei unter https://www.robots.ox.ac.uk/~vgg/data/mview/ verfügbar.
[2]: Die detaillierte Strategie zur Berechnung wird unter https://www.juliahomotopycontinuation.org/examples/computer-vision/ erklärt.
[3]: Siehe https://www.juliahomotopycontinuation.org

Literaturhinweise

Breiding, P.
An algebraic geometry perspective on topological data analysis.
SIAM News 53-1 (2020)
Breiding, P. et. al.
Nonlinear Algebra and Applications.
Numerical Algebra, Optimization and Control. (ePub ahead of print)
Kileel, J.
Algebraic geometry for computer vision.
Dissertation. 2017. Submitted to the University of California, Berkeley
Michalek, M. ; Sturmfels, B.
Invitation to Nonlinear Algebra.
AMMS Graduate Studies in Mathematics. Volume 211 (2021)
Sommese, A.; Wampler, C.
The numerical solution of systems of polynomials arising in engineering and science.
World Scientific. (2005)

Weitere interessante Beiträge

Zur Redakteursansicht