AF: Small: Collaborative Research: Certification for Semi-Algebraic Sets with Applications

传统上，计算机可以非常快速地计算有限位数的数字，以获得精确到一定精度的答案，或者它们可以更慢地操作公式和符号来获得精确的答案。最近，一类新的算法，称为数值路径跟踪算法，已经成功地应用于代数几何、组合学和优化问题的近似解，这些问题曾经被认为是纯粹的符号性质。这种数值计算的结果通常没有得到证明，因为它们是使用启发式方法生成的，这种方法将输入的非连续性质放宽为连续性质。本研究项目的目的是为这些非连续问题提供认证技术，并证明证书可以在给定数值数据的情况下计算，而不需要太多额外的工作。该研究的一个重要组成部分和动力是在其他领域的各种应用领域，如可靠几何计算中的有效处理奇点，半定规划的最优证明，化学反应网络中多重稳定性的证明，以及机构设计中的异常运动。通过调查可认证方法的实际限制，该项目旨在帮助专家决定何时可以将认证方法应用于他们的目的。此外，通过开发新方法来减少认证和非认证版本之间的差距，研究人员将在更多的计算中获得认证方法的保证。教育和研究的整合对于这项提案的成功至关重要，该项目支持将研究生和本科生纳入研究团队。本研究的重点是证明和提高多项式方程和具有精确系数的不等式的处理，这些方程和不等式的退化解只有近似已知。困难在于，在许多情况下，精确系统的根在系数的扰动下表现为不连续的。因此，在这些不连续的情况下，传统的数值证明方法，如区间算法或α -理论，不能单独工作。研究这些退化情况是本项目的主要课题，其基本思想是将数值证明技术与符号计算相结合。该项目将使用从数值数据中获得的见解来大幅提高精确，符号对象计算的复杂性，反过来，使用符号计算的见解来将不适定问题转化为适定问题。与纯符号方法相比，使用成功早期终止的符号-数值混合方法旨在降低复杂性。正则化/压缩奇异根的新技术将简化与奇点相关的计算，并改进应用，包括在真实表面上的奇异曲线的可视化。此外，该项目将通过利用对称性来提高认证例程的复杂性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Traditionally, computers can very quickly calculate with numbers that have a limited number of digits to get answers that are accurate to a certain precision, or they can much more slowly manipulate formulas and symbols to get exact answers. Recently, a new class of algorithms, called numerical path following algorithms, have been successfully applied to approximate solutions for problems in algebraic geometry, combinatorics, and optimization that were once thought to be purely symbolic in nature. The results of such numerical computations are typically not certified, as they are generated using heuristic methods that relax non-continuous properties of the input into continuous ones. The aim of this research project is to give certification techniques for these non-continuous problems and demonstrate that certificates can be computed with not too much extra work given numerical data. An essential part and motivation for this research is a variety of application areas in other fields such as efficiently handling singularities in reliable geometric computation, certification of optima for semidefinite programs, proving existence of multistability in chemical reaction networks, and exceptional motion in mechanism design. By investigating the practical limits of certifiable methods, this project aims to help specialists decide when they can apply certification methods for their purposes. Moreover, by developing new methods that reduce the gap between certified and non-certified versions, researchers will have the guarantee of certified methods in more of their computations. Integration of education and research is essential to the success of this proposal with this project supportingthe inclusion of graduate and undergraduate students in the research team.The focus of this research is to certify and enhance the handling of polynomial equations and inequalities with exact coefficients which have degenerate solutions known only approximately. The difficulty is that, in many cases, the roots of the exact system behave discontinuously under perturbations of the coefficients. Hence, in these non-continuous cases, traditional numerical certification methods, such as interval arithmetic or alpha-theory, cannot work alone. The study of these degenerate cases is the main topic of this project with the fundamental idea to combine numerical certification techniques with symbolic computations. This project will use insights gained from numerical data to drastically improve the complexity of the computation of exact, symbolic objects, and in turn, use insights from symbolic computation to turn an ill-posed problem into a well-posed one. The hybrid symbolic-numeric approach, using early termination upon success, aims to reduce the complexity in comparison with purely symbolic methods. New techniques for regularizing/deflating singular roots will simplify computations related to singularities and improve applications including the visualization of singular curves lying on a real surface. Additionally, this project will improve the complexity of certification routines by exploiting symmetry.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.