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

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 supporting

the 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.