Solving Systems of Polynomial Equations

Systems of polynomial equations arise naturally from many problems in applied mathematics and engineering. Examples of such problems come from robotics, chemical engineering, computer vision, dynamical systems theory, signal processing and geometric modeling, among others. The numerical solution of systems of polynomial equations is considered a challenging problem in computational mathematics. Important classes of existing methods are algebraic methods, which solve the problem using eigenvalue computations, and homotopy methods, which track solution paths in a continuous deformation of the system. In this text, we propose new algorithms of both these types which address some of the most important (numerical) shortcomings of existing methods.

Classical examples of algebraic techniques use Gröbner bases, border bases or resultants. These methods take advantage of the fact that the solutions are encoded by the structure of an algebra that is naturally defined by the equations of the system. In order to do computations in this algebra, the algorithms choose a representation of it which is usually given by a set of monomials satisfying some conditions. In this thesis we show that these conditions are often too restrictive and may lead to severe numerical instability of the algorithms. This results in the fact that they are not feasible for finite precision arithmetic. We propose the framework of truncated normal forms to remedy this and develop new, robust and stabilized methods. The framework generalizes Gröbner and border bases as well as some resultant based algorithms. We present explicit constructions for square systems which show `generic' behavior with respect to the Bézout root count in affine space or the Bernstein-Khovanskii-Kushnirenko root count in the algebraic torus. We show how the presented techniques can be used in a homogeneous context by introducing homogeneous normal forms, which offer an elegant way of dealing with solutions `at infinity'. For instance, homogeneous normal forms can be used to solve systems which define finitely many solutions in projective space by working in its graded, homogeneous coordinate ring. We develop the necessary theory for generalizing this approach to the homogeneous coordinate ring (or Cox ring) of compact toric varieties. In this way we obtain an algorithm for solving systems on a compactification of the algebraic torus which takes the polyhedral structure of the equations into account. This approach is especially effective in the case where the system defines solutions on or near the boundary of the torus in its compactification, which typically causes difficulties for other solvers. Each of the proposed methods is tested extensively in numerical experiments and compared to existing implementations.

Homotopy methods are perhaps the most popular methods for the numerical solution of systems of polynomial equations. One of the reasons is that, in general, their computational complexity scales much better with the number of variables in the system than that of algebraic methods. However, the reliability of these methods depends strongly on some design choices in the algorithm. An important example is the choice of step size in the discretization of the solution paths. Choosing this too small leads to a large computational cost and prohibitively long computation times, while choosing it too large may lead to path jumping, which is a typical cause for missing solutions in the output of a homotopy algorithm. In this thesis, a new adaptive step size path tracking algorithm is proposed which is shown to be much less prone to path jumping than the state of the art software.