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.