CNACS - Calcul numérique certifié pour des courbes algébriques singulières

Coordinateur : Florent Bréhard CNRS CRIStAL

Équipe : CFHP du Groupe Thématique : CO2.

Dates : 12/24 - 12/28

Résumé :

Les courbes algébriques réelles et complexes interviennent dans de nombreuses applications en mathématiques, physique et ingénierie : preuve automatique en géométrie, conception assistée par ordinateur, planification de mouvement en robotique, équations d’ondes non linéaires, etc. Leur manipulation algorithmique est un sujet central en géométrie algébrique effective. Une attention particulière doit être portée aux points singuliers de la courbe car les algorithmes conçus pour les courbes régulières peuvent présenter un comportement erratique (division par zéro, instabilité numérique, etc). Cependant, le traitement purement symbolique des singularités grâce à l’algorithme de Newton-Puiseux n’est souvent pas possible en raison de son coût trop élevé dans beaucoup d’applications.

Le projet CNACS vise la conception d’algorithmes symboliques-numériques pour les courbes algébriques singulières à la fois efficaces et fiables grâce aux techniques du calcul numérique validé. La clé de voûte sera un algorithme de Newton-Puiseux symbolique-numérique pour "déplier" les singularités et paramétrer les branches à l’aide de séries de Puiseux à coefficients intervalles (réels ou complexes). Nous l’utiliserons ensuite comme brique de base pour améliorer la complexité d’algorithmes en géométrie algébrique effective, comme les requêtes de connexité et la topologie de courbes réelles, ou le calcul de la monodromie de courbes algébriques complexes vues comme surfaces de Riemann.

Les résultats attendus sont les suivants :
– Des algorithmes soigneusement étudiés du point de vue de leur complexité (binaire) et de la stabilité numérique.
– Des implémentations open-source soignées, efficaces et fiables, écrites en Julia ainsi qu’une formalisation dans l’assistant de preuve formelle Coq.
– Des applications à des problèmes où interviennent des courbes algébriques singulières comme la planification de mouvement en robotique ou les équations KdV et KP en physique des ondes non linéaires.

Abstract :

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 computaion of the monodromy of comples 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 Cop 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.