Collaborative Research: AF: Small: Real Solutions of Polynomial Systems

科学、工程和工业中的许多问题都可以表示为计算非线性多项式方程组的实数解。一些例子包括为机器人合成执行给定任务的机械连杆，分析化学反应网络，以及计算生物过程中的分叉。由于这种无处不在的情况，人们强烈需要解决在现实世界中自然出现的许多大型系统。这个项目旨在开发新的算法方法来有效和严格地计算真实的解，并在科学和工程中的各种问题上测试这些新方法。此外，该项目将直接支持研究生和本科生的培训和指导，并将通过与该研究项目相关的计算实代数几何的课程开发影响许多其他学生。该项目的技术目标分为两个方面。第一个推力是开发高效而严格的算法，用于计算只有有限多个解的多项式方程组的实数解。这个项目专注于开发新的数学理论和算法，使用同伦延拓来计算至少一个或所有实数解，而不需要计算所有复数解。对于许多现实世界中感兴趣的问题，复杂解的数量比实数解的数量大许多个数量级，因此避免非实数解有利于算法效率。第二个推力开发了一个算法，用于对具有无穷多个解的多项式系统的实解集的每个连通分量中的光滑点进行采样。通过减少样本点，从第一推力开始的算法可以应用于这样的正维系统。此外，对真实光滑点进行采样对于确定真实解决方案集的维度和确定连通性很有用。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Many problems in science, engineering, and industry can be formulated as computing real solutions to systems of nonlinear polynomial equations. Some examples include synthesizing a mechanical linkage for a robot to perform given tasks, analyzing chemical reaction networks, and computing bifurcations in a biological process. Due to this ubiquity, there is a strong demand to tackle many large systems that naturally arise in real world settings. This project aims to develop new algorithmic approaches for efficiently and rigorously computing real solutions and test these new approaches on a variety of problems in science and engineering. Furthermore, this project will directly support the training and mentoring of graduate and undergraduate students, and will impact many other students through curriculum development in computational real algebraic geometry related to this research project. The technical aims of this project are divided into two thrusts. The first thrust develops efficient and rigorous algorithms for computing real solutions to systems of polynomial equations that have only finitely many solutions. This project focuses on developing new mathematical theories and algorithms using homotopy continuation for computing either at least one or all real solutions without needing to compute all complex solutions. For many real world problems of interest, the number of complex solutions is many orders of magnitude larger than the number of real solutions so avoiding non-real solutions is beneficial for algorithmic efficiency. The second thrust develops an algorithm for sampling smooth points in each connected component of the set of real solutions for polynomial systems with infinitely many solutions. By reducing to sample points, the algorithms from the first thrust can be applied to such positive dimensional systems. Moreover, sampling real smooth points is useful for determining the dimension of the real solution set and deciding connectedness.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.