Polynomial Homotopy Continuation: Under the Hood

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

Systems of polynomial equations are ubiquitous in mathematical models in science and engineering. The field of algebraic geometry, which studies solutions to such systems, has the potential to improve techniques for practical numerical investigations of these systems. This research project aims to apply algebraic geometry to advance numerical algorithms for solving systems of polynomial equations. The research includes developing new homotopy continuation methods that exploit the action of the monodromy group, random walk homotopies, and hybrid algorithms for solving sparse systems. The new theoretical framework and algorithms will be implemented in open-source software. Homotopy continuation algorithms are a backbone of modern nonlinear algebra, the art of solving systems of equations that are not necessarily linear. The main strength of these algorithms is in approximate computation, which often is much faster than classical exact techniques and allows tackling problems in high-dimensional spaces. Homotopy continuation methods solve a problem A in three steps: (1) look for a problem B in the same family of problems as A, but with a simpler structure; (2) construct solutions to that simpler problem B; (3) connect A and B with a homotopy, that is, a continuous deformation, and track how solutions of B morph into solutions of A. This project aims to develop a novel framework for basic homotopy continuation routines. One major point is that randomizing numerical algorithms to a greater extent makes them even faster and more robust without a costly increase in computational precision. Another point is that, looking to minimize computational costs, we should invent new hybrid methods intertwining exact and approximate techniques originating in different areas of mathematics. The symbiosis of symbolic, combinatorial, and numerical ideas is the key to the new methods for solving sparse systems. Tools from tropical geometry and numerical algebraic geometry will deliver a generalization of polyhedral homotopy algorithms and lead to a faster polynomial system solver that benefits from a tighter solution count.