Fast polynomial computations with space constraints

Cette thèse d'habilitation présente des algorithmes à la fois rapides et économes en mémoire pour le calcul polynomial, en abordant à la fois les contraintes d'espace lors des opérations fondamentales et le traitement efficace des polynômes creux, notamment via une première méthode d'interpolation quasi-linéaire.

L'essentiel

🎩 Le Magicien des Polynômes : Bruno Grenet et ses deux grands défis

Imaginez que les polynômes (ces expressions mathématiques comme $3x^5 + 2x + 1$) soient des châteaux de cartes.

• Un polynôme dense, c'est un château énorme où chaque carte est posée, même si beaucoup sont blanches. C'est lourd à manipuler.
• Un polynôme sparse (ou "lacunaire"), c'est un château où il y a des milliers d'espaces vides entre quelques cartes colorées. C'est très léger, mais si vous essayez de le manipuler comme un château dense, vous allez gaspiller une énergie folle pour déplacer le vide.

Bruno Grenet, dans ce document (son mémoire d'habilitation), nous raconte comment il a appris à construire des algorithmes (des recettes de cuisine mathématique) pour manipuler ces châteaux de cartes de deux façons très spécifiques : en économisant l'espace et en profitant du vide.

---

🏗️ Partie 1 : La Cuisine en "Micro-Cuisine" (Économie d'espace)

Le problème :
Depuis les années 60, les mathématiciens ont inventé des recettes ultra-rapides pour multiplier ou diviser ces polynômes. Mais il y a un prix à payer : ces recettes rapides demandent une énorme cuisine (beaucoup de mémoire RAM) pour poser les ingrédients intermédiaires. C'est comme vouloir faire un gâteau géant dans un four micro-ondes : ça va vite, mais il faut une cuisine de taille industrielle.

La solution de Bruno :
Il s'est demandé : "Peut-on faire ces recettes ultra-rapides dans une toute petite cuisine, voire même sur un comptoir de 1 mètre carré ?"

Il a développé des techniques astucieuses :

1. Le recyclage intelligent : Au lieu de jeter les vieux ingrédients pour en mettre de nouveaux, il réutilise les mêmes bols. Il nettoie et remplit en temps réel.
2. La réversibilité : Imaginez que vous construisiez un mur de briques. Normalement, vous avez besoin d'un tas de briques à côté. Bruno apprend à construire le mur, puis à le déconstruire briques par briques pour les réutiliser immédiatement ailleurs, sans jamais avoir besoin d'un tas de stockage.
3. L'effet "Cumul" : Au lieu de dire "Je mets le résultat dans un nouveau bol", il dit "Je rajoute le résultat directement dans le bol de départ".

Le résultat ?
Il a prouvé qu'on peut faire des calculs mathématiques complexes (multiplication, division) aussi vite que les méthodes classiques, mais en utilisant presque zéro mémoire supplémentaire. C'est comme si vous pouviez cuisiner un banquet entier sans avoir besoin d'un deuxième comptoir.

---

🕳️ Partie 2 : La Chasse aux Trésors Cachés (Polynômes "Sparse")

Le problème :
Revenons à nos châteaux de cartes. Si votre polynôme a 1000 termes, mais que 999 sont nuls (des zéros), le dire à l'ordinateur "voici 1000 nombres" est stupide. C'est comme envoyer une lettre de 1000 pages où 999 pages sont blanches. Les algorithmes classiques ne voient pas le vide, ils traitent tout, ce qui est lent et inefficace.

La solution de Bruno :
Il faut apprendre à l'ordinateur à ignorer le vide et à se concentrer uniquement sur les cartes colorées (les termes non nuls).

1. L'Interpolation Sparse (Le détective) :
   Imaginez que vous avez un mot de passe caché dans un livre de 1 million de pages, mais vous savez qu'il n'y a que 5 lettres importantes. Au lieu de lire page par page, Bruno a inventé une méthode (inspirée de la transformée de Fourier, mais pour les trous) qui permet de deviner ces 5 lettres en faisant très peu de devinettes. C'est le premier algorithme "quasi-linéaire" (très rapide) pour retrouver ces polynômes cachés.

2. La Multiplication et la Division :
   Multiplier deux polynômes "vides" est un cauchemar : le résultat peut exploser en taille ou, au contraire, s'annuler miraculeusement (des termes positifs et négatifs qui s'annulent). Bruno a créé des méthodes pour deviner la taille du résultat, le calculer, et vérifier instantanément si on a eu raison, sans avoir à tout recalculer.

3. Les Facteurs (La décomposition) :
   Il a aussi travaillé sur la façon de décomposer ces polynômes en morceaux plus petits (comme décomposer un nombre en facteurs premiers), même quand ils sont très "vides".

---

🌍 Pourquoi est-ce important pour vous ?

Même si vous ne faites pas de mathématiques pures, ces travaux touchent votre quotidien :

• 🔒 La Cryptographie : Vos codes bancaires et les communications sécurisées reposent sur des calculs de polynômes. Si on peut les faire plus vite et avec moins de mémoire, on peut sécuriser des systèmes sur des appareils plus petits (comme des cartes à puce ou des capteurs IoT).
• 📡 Les Codes Correcteurs d'Erreurs : Quand vous téléchargez un fichier ou regardez un DVD rayé, des algorithmes de polynômes réparent les données manquantes. Des algorithmes plus rapides et moins gourmands en mémoire rendent ces réparations plus efficaces.
• 🤖 L'Intelligence Artificielle et la Robotique : La manipulation de données complexes nécessite des calculs rapides. Réduire la mémoire nécessaire permet d'intégrer des systèmes plus intelligents dans des robots moins chers et plus autonomes.
• 💻 L'Écologie Numérique : Moins de mémoire utilisée signifie moins d'énergie consommée par les serveurs. C'est un pas vers un calcul plus "vert".

🎯 En résumé

Bruno Grenet nous dit essentiellement : "Pourquoi gaspiller de la mémoire et du temps à traiter le vide ?"
Il a démontré qu'on peut être rapide (comme un Ferrari) tout en étant compact (comme une voiture électrique), et qu'on peut ignorer le vide pour ne traiter que l'essentiel. C'est une révolution dans la façon dont les ordinateurs "pensent" les mathématiques.

Résumé technique

1. Problématique et Contexte

Le domaine de l'algèbre informatique (computer algebra) a vu le développement d'algorithmes extrêmement efficaces pour les opérations polynomiales de base (multiplication, division, interpolation) depuis les années 1960, souvent avec une complexité temporelle quasi-linéaire. Cependant, ces algorithmes rapides (comme ceux basés sur la FFT ou Karatsuba) nécessitent généralement une complexité spatiale linéaire (ou pire) par rapport à la taille des entrées.

Ce travail se concentre sur deux axes majeurs où la contrainte d'espace est critique :

1. Contraintes de mémoire des algorithmes : Comment maintenir une complexité temporelle quasi-linéaire tout en réduisant l'utilisation de la mémoire à une constante (ou logarithmique) ?
2. Représentation des données : Comment traiter efficacement les polynômes creux (sparse) ? Les algorithmes classiques supposent une représentation dense (liste complète des coefficients), ce qui est inefficace pour les polynômes ayant peu de termes non nuls par rapport à leur degré.

2. Méthodologie et Modèles de Calcul

L'auteur définit et analyse plusieurs modèles de calcul pour formaliser la complexité espace-temps :

• Modèles d'accès mémoire :

  • ro/wo (Read-Only / Write-Only) : Modèle théorique standard où les entrées sont en lecture seule et les sorties en écriture seule. Ce modèle impose des bornes inférieures quadratiques pour la multiplication, rendant les algorithmes rapides impossibles.
  • ro/rw (Read-Only / Read-Write) : Les entrées sont en lecture seule, mais les sorties peuvent être lues et écrites. C'est un modèle plus réaliste où l'espace de sortie peut servir d'espace de travail.
  • rw/rw (Read-Write / Read-Write) : Modèle le plus permissif, permettant de réécrire les entrées (calculs in-place). C'est dans ce modèle que les résultats les plus forts sont obtenus.

• Techniques algorithmiques clés :

  • Principe de transposition : Relie la complexité d'un calcul linéaire à celle de son transposé.
  • Réversion (Reversion) : Transformation de programme inversant l'ordre des registres.
  • Calculs cumulatifs et in-place : Utilisation d'opérations comme h += f * g pour réutiliser l'espace mémoire sans allocation supplémentaire.
  • Interpolation creuse (Sparse Interpolation) : Reconstruction d'un polynôme à partir de ses évaluations ou d'un programme linéaire (SLP), jouant un rôle analogue à la FFT pour les polynômes denses.

3. Contributions Majeures et Résultats

Le document est divisé en deux parties principales.

Partie I : Calculs polynomiaux rapides et économes en espace

L'objectif est de concevoir des algorithmes qui sont à la fois rapides (complexité temporelle quasi-linéaire) et constants en espace (ou utilisant uniquement la pile d'appel logarithmique).

• Multiplication et produits partiels :

  • L'auteur démontre que toute multiplication polynomiale utilisant un espace linéaire peut être transformée en une variante à espace constant avec la même complexité temporelle asymptotique dans le modèle ro/rw (pour les produits complets, inférieurs, supérieurs et moyens).
  • Dans le modèle rw/rw, des algorithmes cumulatifs et in-place sont développés pour la multiplication (variantes de Karatsuba et FFT), l'inversion de séries formelles et la division euclidienne.
  • Résultat clé : Il est possible de calculer le reste d'une division euclidienne ou un produit modulaire en espace constant (algébrique) et temps quasi-linéaire, en utilisant des techniques de pré/post-addition et de réversibilité.

• Évaluation multipoint et interpolation :

  • Des algorithmes à espace constant sont proposés pour l'évaluation multipoint et l'interpolation, bien que la constante cachée dans la complexité temporelle soit élevée par rapport aux algorithmes denses standards.

• Automatisation et Algèbre Linéaire :

  • Une méthode automatique est présentée pour convertir des algorithmes bilinéaires standards (comme Strassen-Winograd pour la multiplication matricielle) en versions à espace constant dans le modèle rw/rw.
  • Signification : Cela permet d'obtenir des algorithmes de multiplication matricielle rapides et in-place, réduisant l'empreinte mémoire sans sacrifier la vitesse asymptotique.

Partie II : Calculs sur les polynômes creux (Sparse)

Cette partie traite des polynômes où la plupart des coefficients sont nuls. La représentation utilisée est la liste des termes non nuls (coefficient, exposant).

• Interpolation Creuse :

  • Problème : Reconstruire un polynôme $f$ de sparsité $t$ et de degré $d$ à partir d'entrées implicites (boîte noire ou programme linéaire).
  • Résultat majeur : L'auteur présente le premier algorithme quasi-linéaire pour l'interpolation de polynômes à coefficients entiers.
  • Méthode : Combinaison de la méthode de Prony (via des évaluations sur des racines de l'unité) et de la réduction modulo $x^p - 1$ (folding). L'algorithme gère les cas "équilibrés" (coefficients de taille similaire) et "déséquilibrés" (coefficients de tailles très variables) en utilisant une approche top-down pour isoler les grands coefficients.
  • Limites : Pour les corps finis, l'interpolation quasi-linéaire reste un problème ouvert, principalement à cause de la difficulté du calcul des logarithmes discrets et de la recherche de racines.

• Arithmétique Creuse :

  • Multiplication : Un algorithme probabiliste (type Atlantic City) est proposé pour la multiplication de polynômes entiers creux. Il est sensible à la taille de sortie et utilise une vérification rapide de produits modulaires pour valider les résultats.
  • Division et Divisibilité : Des algorithmes sont développés pour la division exacte et le test de divisibilité. Le test de divisibilité est résolu pour des diviseurs ayant une structure spécifique (gaps importants entre les termes).
  • Factorisation : Une réduction est établie pour le calcul des facteurs de bas degré de polynômes multivariés creux vers le cas univarié et la factorisation de bas degré, en utilisant des séries de Puiseux et des théorèmes de type "Gap".

• Vérification de Produits :

  • De nouveaux algorithmes de vérification de produits polynomiaux (dense et creux) sont développés, basés sur l'évaluation modulo $x^p - 1$ et l'utilisation de matrices compagnons, permettant une complexité linéaire ou quasi-linéaire en taille d'entrée.

4. Signification et Perspectives

• Impact Théorique : Ce travail comble un fossé important entre la complexité temporelle et spatiale en algèbre informatique. Il montre que la contrainte d'espace n'implique pas nécessairement une dégradation temporelle majeure, remettant en cause certaines bornes inférieures du modèle standard ro/wo.

• Applications Pratiques :

  • Cryptographie et Codes Correcteurs : L'interpolation creuse est liée au problème de décodage de syndrome (Syndrome Decoding Problem), crucial pour les cryptosystèmes comme Niederreiter et les protocoles de recherche privée (PIR).
  • Calcul Haute Performance : Les algorithmes in-place réduisent les allocations mémoire, ce qui peut améliorer les performances sur les architectures modernes où la hiérarchie mémoire est un goulot d'étranglement.
  • Calcul Quantique : Les algorithmes réversibles développés dans le modèle rw/rw sont directement applicables au calcul quantique, où le nombre de qubits auxiliaires (ancilla) est une ressource critique.

• Problèmes Ouverts :

  • Existence d'un algorithme d'interpolation creuse quasi-linéaire pour les corps finis.
  • Complexité du test de divisibilité général pour les polynômes creux.
  • Amélioration des constantes cachées dans les algorithmes d'espace constant pour les rendre compétitifs en pratique.
  • Extension des résultats aux polynômes avec coefficients et exposants déséquilibrés simultanément.

En conclusion, cette habilitation présente une avancée significative dans la compréhension et la conception d'algorithmes polynomiaux optimaux en espace, offrant des solutions concrètes pour le calcul sur les polynômes creux et ouvrant de nouvelles voies pour l'algèbre linéaire structurée et le calcul quantique.