Certification Algorithms for Polynomial System Solving

Clemson University, Clemson SC

Investigators

Abstract

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.