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

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

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.