Certification Algorithms for Polynomial System Solving

认证算法是保证在现实世界的计算机上实现时永远不会产生错误答案的计算。这些算法在计算的正确性至关重要并且不能容忍错误的任何设置中都很重要。 这些算法在许多领域都有潜在的应用，包括优化、自动化和图形学。 例如，对于自动驾驶汽车，决策算法不出错至关重要。 例如，如果一个未经认证的算法错过了一个小但重要的细节，汽车可能无法通过间隙或导致事故。随着这种类型的自动化变得越来越普遍，对相应的认证计算的需求将增加。 在这个特定的项目中的工作涉及设计，开发和实施有效的认证方法，以找到多项式系统的共同解决方案。 本项目中描述的算法的开发填补了数值代数几何领域的一个空白，因为以前的方法要么是未经认证的，即，在某些情况下可能会犯错误，或不切实际的认证方法，即，在实际情况下，要花很长时间才能得出答案。 本项目的工作旨在解决这些问题，即，要实用和认证。对于许多计算，算法只能产生近似的真实答案。 认证算法不仅从计算中产生最终结果，而且还提供最终答案与真实答案之间的误差估计。 开发认证算法是计算数学和计算机科学的一个（新）挑战。一个经过认证的算法，首先，必须被证明是正确的，当假设一台计算机可以表示所有的真实的数字。其次，当允许的数字近似于计算机上可以表示的更小的数字集时，必须证明算法的正确性。 因此，认证方法中的两个主要挑战可以总结为：（1）由于许多问题涉及离散化连续变量，因此必须开发理论以确保离散化的选择不会错过离散步骤之间的任何有趣行为;（2）由于并非所有真实的数字都可以在计算机上表示，因此必须开发所有测试和计算以使用近似值，但仍然产生关于潜在的真实的数字的有意义的数据。 该项目涉及设计，实施和开发一个有效的和认证的同伦连续算法的尺寸大于一。 这项工作概括了PI在单变量情况下开发的初步探索和实施。 这个原型是非常有效的，因为它使用了新的子程序，基于间隔的方法，这比以前的approaches.This奖项更灵活，反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

Certified algorithms are computations that are guaranteed to never produce a wrong answer when implemented on a real-world computer. These algorithms are important in any setting where the correctness of a computation is critical and errors cannot be tolerated. Such algorithms have potential applications in many fields, including optimization, automation, and graphics. For example, with self-driving cars, it is vital that the decision-making algorithms do not make errors. For instance, if a non-certified algorithm were to miss a small, but important detail, a car might not fit through a gap or cause an accident. As this type of automation becomes more common, the need for corresponding certified computation will increase. The work in this particular project involves the design, development, and implementation of efficient certified methods for finding common solutions to systems of polynomials. The development of the algorithms described in this project fills a current gap in the field of numerical algebraic geometry since previous approaches are either non-certified, i.e., may make mistakes in some cases, or impractical certified methods, i.e., take too long to produce an answer in practical situations. The work in this project is intended to solve these problems, i.e., to be practical and certified. For many computations, algorithms can only produce an approximation to the true answer. Certified algorithms not only produce a final result from a computation, but they also provide estimates on the error between the final answer and the true answer. Developing certified algorithms is a (new) challenge for computational mathematics and computer science. A certified algorithm must, first, be proved to be correct when assuming that a computer can represent all real numbers. Second, the correctness of the algorithm must be justified when the allowed numbers are approximated by the much smaller set of numbers that can be represented on a computer. Therefore, two of the main challenges in certified methods can be summarized as (1) Since many problems involve discretizing a continuous variable, the theory must be developed to ensure that the choice of discretization does not miss any interesting behaviors between discrete steps and (2) Since not all real numbers can be represented on a computer, all tests and computations must be developed to work with approximations, but still produce meaningful data about the underlying real number. The project involves the design, implementation, and development of an efficient and certified homotopy continuation algorithm in dimensions greater than one. The work generalizes the preliminary exploration and implementation developed by the PI in the univariate case. This prototype is very efficient because of its use of new subroutines, based on interval methods, which have more flexibility than previous approaches.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.