Description du sujet de thèse

--- Contexte ---

Le calcul formel est la discipline qui s'intéresse à la manipulation algorithmique exacte d'objets mathématiques tels que les polynômes, les matrices ou les nombres algébriques. L'expression « manipulation exacte » recouvre peu ou prou les calculs que pourrait faire un mathématicien avec un papier et un crayon, et s'oppose aux approches à base de discrétisation et d'approximation numérique centrales en calcul scientifique.

Néanmoins, calcul formel et numérique ne sont pas exclusifs. L'approximation numérique à précision arbitraire est une fonctionnalité essentielle des logiciels de calcul formel, et, de plus en plus, ceux-ci offrent des outils de calcul numérique rigoureux, c'est-à-dire où les résultats sont accompagnés de bornes d'erreur. Les techniques en jeu dans le calcul rigoureux et à précision arbitraire se rapprochent de celles du calcul symbolique. Plus largement, les algorithmes dits symboliques-numériques exploitent la complémentarité entre méthodes exactes (plus facilement rigoureuses, mieux à même de traiter les problèmes singuliers ou mal conditionnés) et numériques (souvent plus efficaces et plus largement applicables). C'est ce type d'approches mixte que ce projet de thèse se propose d'explorer.

La question centrale est la résolution numérique efficace des équations différentielles linéaires
(1) a_r(x) y^(r) (x) + ⋯ + a_1(x) y'(x) + a_0 (x) y(x) = 0,
où les fonctions a_i sont typiquement des polynômes à coefficients rationnels. Les équations de ce type sont omniprésentes dans la théorie des fonctions spéciales, et apparaissent naturellement en physique, mais aussi par exemple en combinatoire (séries génératrices différentiellement finies) ou en géométrie algébrique (équations de Picard-Fuchs).

On dispose pour ces équations d'algorithmes de résolution numérique qui vont au-delà des méthodes génériques de l'analyse numérique. Par exemple, il est aujourd'hui bien connu que quand l'équation (1) et le point où l'on veut évaluer sa solution sont fixés, on peut approcher la valeur correspondante avec une erreur absolue d'au plus 2^(-p) en seulement Ο(p log^3 p) opérations quand p→∞. En revanche, la dépendance de ce coût vis-à-vis de la taille de l'équation n'a pas été complètement analysée. Il en va de même de la dépendance vis-à-vis du point d'évaluation, qui met en jeu des phénomènes analytiques subtils quand celui-ci se rapproche d'un point où l'équation est singulière.

L'une des motivations pour analyser en détail le coût de la résolution d'équations différentielles linéaires est que celle-ci constitue une étape pour d'autres algorithmes, y compris des algorithmes dont l'entrée et la sortie sont purement algébriques. En particulier, résoudre numériquement une équation peut servir à la résoudre exactement ! Plusieurs travaux ces dernières années se sont intéressés par exemple à factoriser les opérateurs différentiels linéaires — une étape de la recherche de solutions exacte — à partir de la donnée des matrices de monodromie et des matrices de Stokes de l'équation correspondante, deux familles de matrices qui s'expriment en fonction de valeurs de solutions. L'absence de contrôle sur le coût de l'étape numérique est une des choses qui bloquent l'analyse de complexité de ces algorithmes.

--- Sujet de thèse ---

Cette thèse vise en premier lieu à mieux comprendre la complexité, c'est-à-dire le coût en temps de calcul, de la résolution numérique d'équations de la forme (1). Il s'agit aussi bien d'analyser plus finement les algorithmes connus que si possible de développer de nouveaux algorithmes de meilleure complexité. On pourra notamment s'intéresser aux questions suivantes.
• Borner le coût du calcul des matrices de monodromie ou des matrices de Stokes d'une équation différentielle linéaire en fonction de la taille (ordre, degré, taille des coefficients) de l'équation et de la précision demandée.
• Comprendre comment raffiner ces bornes en présence d'informations sur le comportement analytique des solutions.
• Faire en sorte que les analyses de complexité reflètent le comportement pratique des implémentations, implémenter les nouveaux algorithmes éventuels, exploiter les progrès dans la compréhension des algorithmes dans le développement de solveurs efficaces en pratique.

Un objectif secondaire est de débuter l'étude de la complexité des algorithmes de « résolution exacte » fondés sur le calcul numérique des solutions. Pour chaque problème, par exemple la factorisation d'opérateurs, se posent les questions suivantes :
• Quelle est la précision numérique requise pour garantir que l'on a obtenu le résultat recherché ?
• En fonction de cette précision et au vu des résultats sur la partie résolution numérique, quel est le coût total de l'algorithme ? Comment ce coût se compare-t-il à celui d'algorithmes purement algébriques pour la même tâche ?

Enfin, suivant les centres d'intérêts de la personne recrutée et les premiers résultats obtenus, la recherche pourra s'orienter dans d'autres directions connexes aux précédentes, notamment les suivantes :
• Développer un nouveau solveur efficace à petite et moyenne précision, qui exploite au mieux le parallélisme (SIMD et multiprocesseur) des ordinateurs actuels.
• Mieux cerner le champ d'application de l'approche symbolique-numérique pour la résolution exacte : quand est-ce que cette approche permet d'aller au-delà de ce que permettent les techniques purement algébriques connues ? Dans quels cas est-ce que des calculs numériques en précision finie donnent lieu à des algorithmes complets, et dans quels cas doit-on se contenter de méthodes heuristiques ?

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.