Description du sujet de thèse

--- Description ---

Tant en calcul formel qu'en analyse numérique, la résolution des systèmes d'équations polynomiales est un problème central. En calcul formel, ce problème est souvent abordé à l'aide de techniques dites de réécriture, telles que les bases de Gröbner ou les chaînes régulières. En analyse numérique, l'une des méthodes les plus efficaces utilise des déformations. L'idée est assez simple et fonctionne comme suit.

À partir d'un système d'entrée, on construit d'abord un système « plus simple » avec les « mêmes caractéristiques ». Par exemple, pour le système
P_1(x,y) = x^2 - y^2 + x + 3 = 0
P_2(x,y) = x^2 + 2 x y + 7 y^2 - 8 y + 2 = 0, (1)
on peut prendre
Q_1(x,y) = x^2 - α_1 = 0 (α_1 = 1 + i)
Q_2(x,y) = y^2 - α_2 = 0 (α_2 = 2 - i) (2)
comme système plus simple. Les deux systèmes ont des caractéristiques proches dans le sens où deg Q_1=deg P_1=2 et deg Q_2=deg P_2=2. De ce fait on s'attend à ce qu'ils aient le même nombre de solutions. Par construction, les solutions (x,y) ∈ {(sqrt(α_1), sqrt(α_2)), (sqrt(α_1), -sqrt(α_2)), (-sqrt(α_1), sqrt(α_2)), (-sqrt(α_1), sqrt(α_2))} de (2) sont faciles à obtenir. L'idée principale est maintenant de déformer en continu le deuxième système en le premier système en utilisant l'homotopie suivante :
H_1^t (x,y) = (1-t) P_1(x,y) + t Q_1(x,y) = 0
H_2^t (x,y) = (1-t) P_2(x,y) + t Q_2(x,y) = 0. (3)
En fait, à t=1 et t=0, le système (3) n'est autre que (2) et (1), respectivement. Afin d'obtenir les solutions de (1), il suffit ainsi de suivre les solutions de (3) depuis t=1 jusque t=0, en utilisant une méthode numérique standard. Par exemple, partir d'une solution approchée de (1) au temps t=t_0, on peut obtenir une solution approchée pour le temps t=t_0+δ en appliquant la méthode de Newton sur l'approximation à t=t_0. Il est bien sûr possible de concevoir des méthodes d'ordre supérieur (e.g. de type Euler), qui permettent d'utiliser un pas δ plus grand.

--- Contexte ---

Il existe une abondante littérature sur les homotopies numériques. Les problèmes pratiques ne sont généralement pas génériques, ce qui signifie qu'il peut y avoir plusieurs solutions ou trajectoires de solution z(t) qui partent à l'infini (c'est-à-dire qu'il y a moins de solutions isolées que prévu par la borne de Bézout). Les stratégies spéciales, appelées phases finales (end game, en anglais), doivent être utilisées à proximité du point de référence pour faire face à des solutions multiples. Les trajectoires de solution qui partent à l'infini se produisent généralement pour les systèmes creux, lorsque les supports du polynôme P_k sont spéciaux. Des raffinements de la borne de Bézout existent pour cette situation et des déformations spéciales peuvent être construites afin de préserver les propriétés de support et le
nombre de solutions prévus par cette limite affinée. Enfin, il existe plusieurs techniques pour certifier les solutions numériques à t=0 ou tout au long du chemin.

Dans les cas favorables, les logiciels existants pour les homotopies numériques sont beaucoup plus rapides que les logiciels symboliques pour le calcul des bases de Gröbner. Cependant, beaucoup de choses peuvent mal tourner pendant le suivi numérique des trajectoires : il peut y avoir des singularités sur ou à proximité des chemins, des phases finales pour des multiplicités élevées peuvent entraîner une pénalité de performance importante, la précision de calcul peut être insuffisante, le conditionnement numérique pourrait être mauvais, etc. Les logiciels existants nécessitent généralement un réglage manuel des paramètres internes afin de traiter les
exemples les plus intéressants.

Dans le cadre du projet ERC ODELIX (qui finance cette proposition de thèse), nous nous intéressons aux systèmes polynomiaux vérifiés par des coefficients de séries formelles tronquées, et solutions d'équations différentielles. De tels systèmes ont une structure spéciale que nous souhaitons mieux comprendre et exploiter.

--- Méthodologie ---

La thèse commencera par rassembler la littérature récente sur la résolution numérique des systèmes polynomiaux, ainsi que les principales implantations logicielles. Nous nous concentrerons sur le cas des systèmes homogènes carrés avec des solutions régulières. Plus précisément, la question théorique suivante sera abordée : comment réaliser des suivis de trajectoires fiables de la manière la plus efficace possible ?

La deuxième partie de la thèse sera consacrée à des solutions non régulières (quelles sont les méthodes les plus efficaces pour calculer numériquement des zéros multiples et les certifier ?) et aux systèmes issus d'équations différentielles (comment exploiter cette structure particulière et que devient la complexité des méthodes d'homotopie pour cette application ?).

La partie pratique de la thèse concerne l'implémentation logicielle de méthodes d'homotopie fiables. L'implémentation se fera sous forme d'une bibliothèque dédiée, librement distribuée sous la licence publique générale GNU. Plusieurs outils pour l'arithmétique fiable sont déjà disponibles dans Mathemagix [8, 12, 15], qui peuvent potentiellement être utilisés pour ce travail d'implémentation.

Plus précisément, dans le cadre de cette implantation, nous prévoyons de travailler sur les problèmes suivants :
• Développement d'algorithmes pour l'évaluation efficace des polynômes d'entrée pour divers types de données numériques et fiables, éventuellement en utilisant la génération automatique de code et la compilation à la volée.
• Mise en œuvre de types de données supplémentaires et fiables pour la certification efficace des étapes d'homotopie numérique, telles que des modèles de Taylor et l'arithmétique de boules.
• Mise au point de solveurs par homotopie multi-threads.
• Faire en sorte que les solveurs par homotopie bénéficient d'instructions vectorielles matérielles SIMD (Single Instruction Multiple Data) en utilisant potentiellement les outils existants dans le système Mathemagix.

Contexte de travail

La thèse sera effectuée au laboratoire LIX (Laboratoire d'Informatique de l'École polytechnique), qui se situe dans le bâtiment Alan Turing, 1, rue Honoré d'Estienne d'Orves, Palaiseau. La thèse sera effectuée dans l'équipe MAX de calcul formel et financée par le project ERC ODELIX. La candidate ou le candidat disposera d'un poste de travail et de moyens pour assister à quelques conférences par an.

Contraintes et risques

Néant.