Journée de lancement
27 avril 2021, en ligne
Programme
- 9h30-9h50. Nicolas Brisebarre, Démarrage du projet.
- 10h00-10h45. Jean-Michel Muller, Manipulation de quaternions en arithmétique virgule flottante.
- 11h00-11h45. Fredrik Johansson, Calcium: computing in exact real and complex fields.
- 14h15-15h15. Florent Bréhard (CNRS, CRIStAl, Lille), Intégrales abéliennes et 16e problème de Hilbert : Repousser les limites du calcul numérique certifié.
- 15h30-16h15. Mioara Joldes, A polynomial optimization-based approach for computing the orbital collision probability for long-term encounters.
- 16h30 Clôture de la journée.
Les quaternions permettent de représenter des rotations tridimensionnelles de manière non singulière, à l'aide de 4 paramètres réels. Cette propriété les fait fréquemment utiliser en infographie, ainsi que dans le contrôle des drones et des véhicules aérospatiaux. Les opérations virgule flottante sur les quaternions (addition, multiplication, réciproque, norme, conversion vers/depuis des matrices de rotation) sont souvent mises en œuvre de manière naïve, avec pour conséquence des "débordements parasites" (un calcul intermédiaire va faire un underflow ou un overflow, conduisant à un résultat final calculé soit très imprécis, soit infini, soit de la forme "Not a Number", alors que le résultat exact est dans le domaine des nombres représentables). Notre but est de proposer des solutions de contournement de ce problème, et des alternatives plus précises pour ces opérations.
Ce travail a été fait en collaboration avec Mioara Joldes.
Calcium is a C library for real and complex numbers in a form suitable for exact algebraic and symbolic computation. Numbers are represented as elements of fields Q(a1,...,an) where the extension numbers ak may be algebraic or transcendental. The system combines efficient field arithmetic with automatic construction of fields and ideals of algebraic relations, resulting in a practical computational model of R and C in which equality is rigorously decidable for a large class of numbers which includes Q as a subset.
Les intégrales abéliennes sont des intégrales de fonctions rationnelles le long de courbes algébriques définies implicitement dans le plan. Elles jouent un rôle important dans le seizième problème de Hilbert, puisque leurs zéros correspondent aux cycles limites de certains champs de vecteurs polynomiaux à partir desquels elles sont définies. Ainsi, leur évaluation précise et rigoureuse est cruciale pour nombre de preuves assistées par ordinateur dans ce domaine.
Nous présentons un algorithme de calcul efficace à base de séries de Fourier tronquées pour approcher la courbe, que l'on raffine dans un premier temps par une méthode de Newton, puis que l'on valide a posteriori de sorte à définir un tube très précis autour de cette courbe. Cela nous permet d'évaluer finement l'intégrale abélienne sous forme d'un intervalle contenant la solution exacte.
Au-delà de l'intérêt de ce travail pour le problème considéré, nous souhaitons montrer comment différents outils issus de la théorie de l'approximation, du calcul flottant et du calcul formel se combinent pour donner naissance à des algorithmes symboliques-numériques rigoureux et efficaces. De plus, nous aborderons les défis pour la preuve formelle que soulève notre projet futur d'implémentation en Coq de cette méthode.
Ce travail est une collaboration avec Nicolas Brisebarre, Mioara Joldes et Warwick Tucker.
The computation of long-term collision probability in space encounters is usually formulated as an integral of a multivariate Gaussian distribution over the volume of initial conditions which generate collisions in the considered time interval. This collision set, also called swept-volume in literature, can hardly be determined analytically, without making various simplifications. We propose a method for computing a higher-order outer-approximation of the swept-volume by a polynomial superlevel set, obtained as an optimal solution of a polynomial optimization problem. This has the advantage of providing approximate closed-form descriptions of the collision-prone states which can then be effectively used for long-term and repeated conjunctions analysis. From a computational viewpoint, one has to solve a hierarchy of linear matrix inequality problems of increasing size, which provide approximations (i) of increasing accuracy and (ii) convergent in volume to the original set. Secondly, once such a polynomial representation is computed, a high-order quadrature scheme for volumes implicitly defined by a polynomial superlevel sets is employed. Finally, the method is illustrated on some numerical examples borrowed from the literature. This is a joint work with D. Arzelier, F. Bréhard, J.-B. Lasserre, S. Laurens and A. Rondepierre.
