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

科学、工程和工业中的许多问题都可以表述为计算非线性多项式方程组的真实的解。 一些例子包括为机器人合成机械连杆以执行给定任务，分析化学反应网络，以及计算生物过程中的分叉。 由于这种普遍性，有一个强烈的需求，以解决许多大型系统，自然出现在真实的世界设置。 该项目旨在开发新的算法方法，以有效和严格地计算真实的解决方案，并在科学和工程中的各种问题上测试这些新方法。 此外，该项目将直接支持研究生和本科生的培训和指导，并将通过与本研究项目相关的计算真实的代数几何课程开发影响许多其他学生。 该项目的技术目标分为两个方面。 第一个推力发展的有效和严格的算法计算真实的解决方案的系统的多项式方程，只有许多解决方案。 这个项目的重点是开发新的数学理论和算法，使用同伦连续计算至少一个或所有真实的解决方案，而不需要计算所有复杂的解决方案。 对于许多感兴趣的真实的世界问题，复数解的数量比真实的解的数量大许多数量级，因此避免非真实的解有利于算法效率。 第二个推力开发了一个算法，用于采样光滑点在每个连接组件的一组真实的解决方案的多项式系统无限多的解决方案。 通过减少到样本点，从第一推力的算法可以应用到这样的正维系统。 此外，采样真实的光滑点是有用的，以确定尺寸的真实的解决方案集和决定connecteditions.This奖项反映了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.