Loading…
Thumbnail Image

Numerical nonlinear algebra

Timme, Sascha

Numerical nonlinear algebra is concerned with the development of numerical methods to solve problems in nonlinear algebra. The main computational task is the solution of systems of polynomial equations. In this thesis, we focus on the numerical solution of polynomial systems using homotopy continuation methods. We apply techniques from numerical analysis to obtain a mixed-precision path tracking algorithm specifically designed for the application in polynomial homotopy continuation methods. This algorithm uses an adaptive step size control that builds on a local understanding of the region of convergence of Newton's method and the distance to the closest singularity. Important for the use of numerical nonlinear algebra in mathematical proofs is the possibility to certify that the computed approximate solutions of a polynomial system correspond to true (distinct) solutions of the system. We present a new certification routine based on interval arithmetic and Krawczyk's method that outperforms the state of the art by multiple orders of magnitude. We also demonstrate numerical nonlinear on a range of applications. To illustrate tools and techniques from numerical nonlinear algebra, we consider Steiner's conic problem and give the first fully real instance of Steiner's conic problem using a computer-assisted proof. We study the action of the projective linear group on cubic surfaces. In particular, we compute the degree of the projective variety given by the Zariski closure of the orbit of a general cubic surface. We also consider the maximum likelihood estimation problem for Gaussian models whose covariance matrices lie in a given linear space. Using numerical nonlinear algebra, we compute the ML degree and dual ML degree for various models of linear covariance matrices. Another application is the study from tensegrity frameworks made from rigid bars and elastic cables, depending on many parameters. We use numerical nonlinear algebra to sample the semi-algebraic catastrophe set which characterizes a region of the parameter space that can trigger sudden large-scale shape changes. Finally, we present the software package HomotopyContinuation.jl for the numerical solution of polynomial systems. We describe its functionality, share some of its design and implementation details and demonstrate its impact on the broader research community.
Numerische nichtlineare Algebra beschäftigt sich mit der Entwicklung von numerischen Methoden zur Lösung von Problemen in der nichtlinearen Algebra. In der nichtlinearen Algebra ist die zentrale Berechnungsaufgabe das Lösen von System von polynomiellen Gleichungen ist. In dieser Dissertation fokussieren wir uns auf das Lösen von Polynomsystem mittels Homotopie-Fortsetzungsverfahren. Wir wenden Techniken aus der numerischen Analysis an, um einen gemischte Präzision Pfadverfolgungsalgorithmus zu erhalten, der speziell für die Anforderungen von polynomiellen Homotopie-Fortsetzungsverfahren gestaltet ist. Dieser Algorithmus nutzt eine adaptive Schrittweitensteuerung, welche auf einem lokalen Verständnis der Konvergenzregion vom Newtonverfahren und dem Abstand zur nächsten Singularität basiert. Wichtig für die Anwendung von Methoden der numerischen nichtlinearen Algebra in mathematischen Beweisen ist die Möglichkeit zu zertifizieren, dass die berechneten approximativen Lösungen eines Polynomsystems zu echten (unterschiedlichen) Lösungen des Systems korrespondieren. Wir implementieren eine neue Zertifizierungsmethode basierend auf Intervallarithmetik und dem Krawczyk-Verfahren, welche den aktuellen Stand der Technik um mehrere Größenordnungen schlägt. Wir demonstrieren außerdem numerische nichtlineare Algebra an einer Reihe von Anwendung. Um die Werkzeuge und Techniken der numerischen nichtlinearen Algebra zu demonstrieren, betrachten wir Steiners Kegelschnittproblem und geben die erste komplett reelle Instanz mittels eines computergestützten Beweises an. Wir betrachten die Wirkung der projektiven linearen Gruppe auf kubischen Flächen und berechnen den Grad der projektiven Varietät, die durch den Zariskiabschluss des Orbits einer allgemeinen kubischen Fläche gegeben ist. Wir betrachten zudem das Problem der Maximum-Likelihood Schätzung für Modelle von Gaußschen Verteilungen, dessen Kovarianzmatritzen innerhalb eines gegeben linearen Raums liegen. Mittels numerischer nichtlinearer Algebra berechnen wir den ML Grad und den dualen ML Grad für verschiedene Modelle von linearen Kovarianzmatritzen. Eine weitere Anwendung ist die Untersuchung von Tensegrity Frameworks, welche aus starren Stangen und elastischen Kabeln bestehen. Wir benutzen numerische nichtlineare Algebra, um die semi-algebraische Katastrophenmenge zu samplen, welche die Region des Parameterraums charakterisiert, die plötzliche große Formveränderungen auslösen kann. Abschließend präsentieren wir das Softwarepaket HomotopyContinuation.jl für die numerische Lösung von Polynomsystemen. Wir beschreiben seine Funktionalität, teilen einige der Design- und Implementierungsdetails und demonstrieren seinen Einfluss auf die breitere Forschungsgemeinschaft.