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.