Automated, Secure Homotopy Continuation and Parameter Space Exploration

Colorado State University, Fort Collins CO

Investigators

Abstract

Systems of polynomial equations arise naturally in most scientific and engineering fields. These systems describe the motion of robotic arms, the steady states of biochemical reactions, the location of radio transmitters based on sensor readings, and many other science and engineering scenarios that are rooted in physical laws and geometry. The solution of polynomial systems was nearly impossible until roughly fifty years ago, and efficient methods are still being developed and analyzed. The first broad direction of this project seeks to automate the tuning of some of these methods (so that non-experts can use them readily) and to incorporate more certainty in the computations. The second broad direction seeks to further develop methods that are particularly useful in applications and to make progress on a few particular applications, namely, biochemical reaction networks, geolocation, and population genetics. Three graduate students will be involved in the project. Homotopy continuation is a fundamental computational tool of numerical algebraic geometry, on which virtually all advanced algorithms within the field depend. While there has been much theoretical and algorithmic development on this topic over the years, there are still at least three basic problems to be addressed. First, ill-conditioning forces the use of expensive high-precision numerical computations and sometimes path failure. Second, homotopy continuation depends on a number of numerical tolerances that are highly problem-dependent and difficult to adjust, especially for non-experts. Third, numerical methods are inherently inexact, making them undesirable in some contexts. The three projects of the first research direction seek to make progress on solving these problems. Fundamental scientific and engineering questions frequently involve parameters, and their solution depends on the ability to understand and move around parameter spaces effectively. The three projects of the second direction aim to further develop numerical homotopy methods for parameter space exploration. The first project will advance our ability to collect useful data from Euclidean parameter spaces, particularly when the goal is to find points in parameter space at which a parameterized polynomial system has a special kind of solution set. The second project aims to extend homotopy continuation to general algebraic parameter spaces. The third project is an assortment of applications, as mentioned.