Lösen von polynomiellen Gleichungen

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(x₁,x₂)=x₁²-x₁+x₂+x₁∙x₂=0 eine polynomielle Gleichung, aber 2^x=0 ist keine, da sich die Funktion 2^x nicht als Summe von endlich vielen Produkten von x darstellen lässt. Ein System polynomieller Gleichungen ist ein Gleichungssystem der Form

p₁(x)=…=p_n(x)=0,

wobei p₁, …, p_n allesamt Polynome in n Variablen x=(x₁,…,x_n) sind. Das Problem dieses Gleichungssystem zu lösen, ist, Werte z₁,…, z_n 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=(x₁,x₂,x₃) in ein zweidimensionales Foto y=(y₁,y₂) überführt. Der Mechanismus des Fotografierens wird dabei durch eine rationale Funktion modelliert: y₁=p₁(x)/q₁(x) und y₂=p₂(x)/q₂(x), wobei p₁, p₂, q₁ und q₂ Polynome sind. In anderen Worten, q₁(x)∙y₁ - p₁(x) = q₂(x)∙y₂-p₂(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=(u₁,u₂) und v=(v₁,v₂). 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 (u₁ - y₁)² + (u₂ - y₂)² + (v₁ - z₁)² + (v₂ - z₂)²

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 x₁,…,x_n 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)=(x₁^d₁ - 1, … , x_n^d_n - 1) =0 wählen, wobei d₁ der Grad von p₁(x) ist und so weiter. Der Grad eines Polynoms ist der maximale Wert der Exponentensumme jedes Terms. Beispielsweise hat das Polynom x₁∙x₂+x₁ 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 x₁³-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