Automated, Secure Homotopy Continuation and Parameter Space Exploration

多项式方程组在大多数科学和工程领域中自然出现。 这些系统描述了机械臂的运动、生化反应的稳态、基于传感器读数的无线电发射器的位置，以及许多其他植根于物理定律和几何学的科学和工程场景。 直到大约50年前，多项式系统的解几乎是不可能的，有效的方法仍在开发和分析中。 该项目的第一个主要方向是自动调整其中一些方法（以便非专家可以轻松使用它们），并在计算中加入更多的确定性。 第二个大方向寻求进一步开发在应用中特别有用的方法，并在一些特定应用方面取得进展，即生物化学反应网络，地理定位和群体遗传学。 同伦延拓是数值代数几何的基本计算工具，几乎所有的高级算法都依赖于它。 虽然多年来在这个主题上已经有了很多理论和算法的发展，但仍然有至少三个基本问题需要解决。 首先，病态迫使使用昂贵的高精度数值计算，有时路径故障。 其次，同伦延拓依赖于一些数值公差，这些公差高度依赖于问题，并且难以调整，特别是对于非专家。 第三，数值方法本质上是不精确的，这使得它们在某些情况下不受欢迎。 第一个研究方向的三个项目寻求在解决这些问题方面取得进展。 基本的科学和工程问题经常涉及参数，它们的解决方案取决于理解和有效地移动参数空间的能力。 第二个方向的三个项目旨在进一步发展参数空间探索的数值同伦方法。 第一个项目将提高我们从欧几里德参数空间收集有用数据的能力，特别是当目标是在参数空间中找到参数化多项式系统具有特殊类型解集的点时。 第二个项目的目标是将同伦延拓推广到一般的代数参数空间。 第三个项目是一个应用程序的分类，如前所述。

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.