Certified Numerics for Algebraic Curves with Singularities – CNACS

Real and complex algebraic curves play a crucial role in many applications of mathematics, physics and engineering, like automatic geometric theorem proving, computer-aided geometric design, motion planning in robotics or nonlinear wave equations. Their algorithmic treatment is at the core of computational algebraic geometry.
Singularities are the points where the curve is locally not similar to a line. Particular care
is needed there since algorithms designed for regular curves may exhibit critical behavior at those
points, like division by zero or numerical instability. On the other hand, a purely symbolic treatment of singularities
via the Newton-Puiseux algorithm is often too costly for numerous applications.

The goal of the CNACS project is to design symbolic-numeric algorithms for algebraic curves with singularities which are both efficient (thanks to floating-point computations) and reliable, i.e. with guaranteed error bounds with the use of validated numerics. The cornerstone will be a validated symbolic-numeric Newton-Puiseux algorithm to "unfold" the singularity and parametrize the branches by fractional-exponent power series with real or complex interval coefficients. We will then use this new algorithm as a building block for more efficient algorithms in computational real and complex algebraic geometry such as connectivity queries on real curves, the topology of curves or the computation of the monodromy of complex algebraic curves seen as Riemann surfaces.

The expected outcomes include:
- thoroughly investigated algorithms from a theoretical point of view, with (bit) complexity analysis and numerical stability
- neat open source implementations, both efficient and reliable, written in Julia (??), together with a fully certified implementation formalized in the Coq proof assistant
- applications to problems involving singular algebraic curves, such as motion planning in robotics or the KdV and KP equations for nonlinear wave models in physics