NOUVEAU RECORD POUR MULTIPLIER DES GRILLES DE NOMBRES
Multiplier deux matrices — des grilles de nombres — est l’une des opérations les plus fondamentales de l’informatique. Avec la méthode de l’école, le coût pour deux grilles n sur n croît comme n³. L’algorithme de Volker Strassen, en 1969, a été le premier à faire mieux — « sous-cubique », dit l’article — et depuis, les mathématiciens mesurent les progrès avec un seul nombre : l’exposant ω (oméga), la plus petite puissance de n qui suffit quand les grilles grandissent.
Strassen l’a fait passer sous 2,81. Des décennies de travaux, listés dans l’article, l’ont ramené vers 2,37, par pas de plus en plus petits. En 2026, Emilien Dupont et ses collègues atteignaient 2,371177. Reza Zadeh, de l’entreprise Matroid, Inc., prouve maintenant que ω < 2,37115924.
Quelques améliorations de la borne supérieure de ω, de Strassen en 1969 à cet article. — Tableau 1, Zadeh (2026), arXiv:2610.10593, CC BY 4.0.
Une recette à 212 820 réglages
Ces records ne viennent pas d’une astuce plus maligne pour les petites grilles. Ils viennent d’un objet algébrique appelé tenseur de Coppersmith–Winograd, qu’on peut découper et recombiner, récursivement, en de nombreux produits de matrices indépendants. La façon de le découper dépend d’un immense ensemble de choix : distributions de probabilité, pénalités d’entropie, tailles de matrices définies niveau après niveau. Tout jeu de choix valide donne une borne valide ; tout l’art est d’en trouver un bon.
En s’appuyant sur le cadre de Josh Alman et ses collègues et sur la formulation de Dupont et ses collègues, Zadeh a réglé 212 820 nombres à la fois, avec trois raffinements :
- Une échelle selon l’importance. Certains morceaux de la construction n’apparaissent que rarement : leur effet sur le résultat est minuscule, et un optimiseur les bouge à peine. Chaque nombre a été remis à l’échelle selon le poids de son morceau.
- Six boutons pour les goulots. L’exposant final est fixé par la plus faible de trois quantités concurrentes, à trois étages. Une correction séparée, avec seulement six commandes, les a maintenues en équilibre.
- Un export exact. La recette finale a été convertie en fractions exactes, de dénominateur 2⁹⁶.
La preuve par la vérification
La borne est une preuve assistée par ordinateur. Un petit programme, qui n’utilise que la bibliothèque standard de Python — ni réseau, ni modèle, ni paquet supplémentaire — reconstruit chaque distribution à partir des fractions exactes et évalue le résultat avec des arrondis garantis. Il trouve que la quantité clé est positive, d’environ 8,5 milliardièmes, ce qui prouve la borne. L’auteur souligne ce que cela ne couvre pas : le programme est du code auditable, pas une formalisation de toute la théorie dans un assistant de preuve, et la recherche était locale, sans prétendre que la recette soit la meilleure possible.
L’auteur écrit aussi que des outils d’IA générative, non nommés, ont aidé l’exploration numérique, le logiciel et le manuscrit, et que le code initial s’inspirait de notes de calcul partagées publiquement par Eric Naslund. Un autre certificat informatique public, diffusé le 5 octobre 2026, avait atteint 2,371169353 ; la nouvelle valeur est encore plus basse.
Plus rapide, en théorie
Le gain par rapport à Dupont et ses collègues est de 0,00001776 sur l’exposant. Comme toutes les bornes obtenues ainsi, la garantie est asymptotique : l’exposant seul ne dit pas à partir de quelle taille de matrice le nouvel algorithme battrait réellement les méthodes existantes. Ce qu’il change, c’est la meilleure réponse connue à une question posée depuis 1969 : à quelle vitesse, en principe, peut-on multiplier des grilles de nombres ?