Certification Algorithms for Polynomial System Solving

经过认证的算法是在现实世界的计算机上实现时保证永远不会产生错误答案的计算。这些算法在计算的正确性至关重要且错误不可容忍的任何环境中都是重要的。这些算法在许多领域都有潜在的应用，包括优化、自动化和图形学。例如，对于自动驾驶汽车，至关重要的是决策算法不会出错。例如，如果一个未经认证的算法遗漏了一个很小但很重要的细节，一辆车可能无法通过缝隙或造成事故。随着这种类型的自动化变得越来越普遍，对相应认证计算的需求将会增加。这个特殊项目的工作包括设计、开发和实施有效的认证方法来寻找多项式系统的公共解。本项目中描述的算法的发展填补了数值代数几何领域目前的一个空白，因为以前的方法要么是非认证的，即在某些情况下可能会出错，要么是不实用的认证方法，即在实际情况下需要花费太长的时间来产生答案。本项目的工作就是为了解决这些问题，即实践性和认证性。对于许多计算，算法只能产生与真实答案的近似值。经过认证的算法不仅从计算中产生最终结果，而且还提供对最终答案和真实答案之间的误差的估计。开发经过认证的算法是计算数学和计算机科学面临的(新)挑战。首先，当假设一台计算机可以表示所有实数时，必须证明经过认证的算法是正确的。其次，当允许的数字被计算机上可以表示的小得多的数字集近似时，必须证明算法的正确性。因此，认证方法中的两个主要挑战可以总结为(1)由于许多问题涉及离散化连续变量，所以必须开发理论以确保离散化的选择不会错过离散步骤之间的任何有趣的行为和(2)由于不是所有的实数都可以在计算机上表示，所以所有的测试和计算都必须开发成使用近似值，但仍然产生关于潜在实数的有意义的数据。该项目涉及设计、实现和开发一种有效的、经过验证的同伦延拓算法，其维度大于1。该工作概括了PI在单变量情况下的初步探索和实现。这个原型非常有效，因为它使用了基于区间方法的新子例程，比以前的方法具有更大的灵活性。这个奖项反映了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.