💻 computer science

55 Additions Suffice for 3x3 Matrix Multiplication at Rank 23

Cet article présente un nouvel algorithme de rang 23 pour la multiplication de matrices $3\times3$ qui réduit le nombre d'additions requises à 55 (totalisant 78 opérations scalaires), améliorant ainsi l'état de l'art précédent de 56 additions tout en maintenant la validité sur n'importe quel anneau associatif grâce à une construction basée sur le tenseur de Perminov et un circuit linéaire optimisé.

Auteurs originaux : Samurdhi Karunaratne, Anushka Idamekorala

Publié 2026-08-03

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Samurdhi Karunaratne, Anushka Idamekorala

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un chef étoilé essayant de cuisiner un gâteau massif et complexe. La recette nécessite de mélanger des dizaines d'ingrédients de manières très spécifiques. Dans le monde de l'informatique, « mélanger » les ingrédients revient à multiplier des nombres, et « cuisiner le gâteau » revient à multiplier deux grilles de nombres (des matrices) pour obtenir un nouveau résultat. Pendant longtemps, les mathématiciens ont pensé que la seule façon de faire cela était de suivre la recette standard, la plus lente : multiplier chaque nombre et ensuite les additionner. Mais dans les années 1960, un génie nommé Strassen a découvert un tour de magie. Il a réalisé que si vous réorganisiez l'ordre de votre mélange, vous pourriez éviter certains travaux de force. Vous pouviez obtenir le même délicieux gâteau en effectuant moins de « multiplications », qui sont les étapes les plus coûteuses et les plus chronophages.

Cependant, il y a un piège. Si vous économisez sur les multiplications coûteuses, vous devez souvent effectuer plus d'« additions » (mélanges de bols) pour préparer les ingrédients. Voyez cela comme ceci : au lieu de simplement verser de la farine dans un bol, vous pourriez devoir hacher, remuer et plier les ingrédients selon une danse très spécifique avant de pouvoir les combiner. L'objectif a été de trouver la danse parfaite qui utilise le moins d'étapes possibles. Ce papier que vous allez lire traite d'une équipe qui a trouvé une nouvelle danse légèrement plus efficace pour un type de gâteau spécifique : une matrice 3x3. Ils n'ont pas changé le nombre de levées lourdes (multiplications), mais ils ont réussi à réduire le nombre de étapes de mélange (additions), économisant ainsi une quantité infime mais significative de travail.

La nouvelle danse qui bat des records

Ce papier, écrit par Samurdhi Karunaratne et Anushka Idamekorala de Logical AI, annonce un nouveau record pour la multiplication de deux grilles de nombres 3x3. Ils ont trouvé un moyen de le faire en utilisant seulement 55 additions et 23 multiplications.

Pour comprendre pourquoi c'est important, imaginez la recette record précédente. Le champion actuel, créé par un chercheur nommé Sun, nécessitait 56 additions. Les auteurs de ce papier n'ont pas inventé une toute nouvelle façon de multiplier les matrices ; au contraire, ils ont pris une recette existante et publique (créée par Perminov) qui utilisait 58 additions et 59 additions dans des versions antérieures, et ils ont optimisé les étapes de « préparation ». Ils ont réalisé qu'en réorganisant la façon dont les ingrédients étaient pré-mélangés, ils pouvaient réduire le nombre total d'étapes d'addition à 55.

Voici comment fonctionne leur nouvelle « cuisine », divisée en trois étapes simples :

Préparer les ingrédients de gauche : Avant le mélange, ils prennent la première grille de nombres (appelons-la la grille « Gauche ») et effectuent 13 étapes simples d'addition ou de soustraction pour créer 23 mélanges spéciaux.
Préparer les ingrédients de droite : Ils font la même chose pour la seconde grille de nombres (la grille « Droite »), en utilisant 14 étapes pour créer ses 23 mélanges spéciaux.
Le grand mélange et l'assemblage final : Ils multiplient les mélanges correspondants des grilles Gauche et Droite (23 multiplications au total). Ensuite, ils prennent ces 23 résultats et effectuent 28 autres étapes d'addition pour assembler le résultat final 3x3.

Lorsque vous additionnez le travail de préparation (13 + 14) et l'assemblage final (28), vous obtenez exactement 55 additions. C'est une unité de moins que le record précédent, ce qui en fait la méthode la plus efficace connue pour ce type de calcul spécifique.

Pourquoi cela importe (et pourquoi cela n'importe pas)

Vous vous demandez peut-être : « Est-ce la meilleure façon absolue de le faire ? » Les auteurs sont très prudents et précisent : Non, pas nécessairement. Ils ont prouvé que pour cet arrangement spécifique d'ingrédients qu'ils ont choisi, 55 est le meilleur score possible. Ils ont utilisé une recherche mathématique rigoureuse pour prouver qu'on ne peut pas se contenter de moins d'étapes pour cette recette spécifique. Cependant, ils admettent qu'il pourrait exister une recette complètement différente (un arrangement d'ingrédients différent) qui pourrait être encore plus rapide. Ils ne l'ont pas encore trouvée, et ils ne prétendent pas avoir résolu le mystère entier de la multiplication matricielle pour toujours.

Ils précisent également qu'il ne s'agit pas d'une simple supposition chanceuse ou d'une simulation informatique qui pourrait être erronée. Ils ont fourni un « certificat » de vérité. Ils ont écrit toute la recette étape par étape (appelée un « programme en ligne directe ») et l'ont passée à travers plusieurs programmes informatiques indépendants (écrits en Python et Node.js) pour vérifier chacune des 729 règles mathématiques qui doivent être vraies pour que la recette fonctionne. Chaque vérification a réussi. Cela signifie que les mathématiques sont solides et que la recette fonctionne parfaitement pour n'importe quel système de nombres, même les plus étranges où l'ordre de la multiplication compte.

L'IA derrière le rideau

Un tournant intéressant dans cette histoire est la manière dont la recette a été découverte. Les auteurs révèlent qu'un chercheur humain a guidé un système d'IA (plus précisément, un agent utilisant le GPT-5.6 Sol d'OpenAI) pour la découvrir. L'humain a fixé l'objectif : « Trouvez un moyen de battre le record de 56 additions. » L'IA a ensuite exploré le paysage des recettes existantes, a trouvé la version de Perminov avec 58 additions, et a réalisé qu'en ajustant les étapes de préparation, elle pouvait économiser trois mouvements supplémentaires. L'IA a ensuite vérifié son travail, a écrit le code et a vérifié les mathématiques. C'est un exemple parfait de la collaboration entre l'homme et la machine : l'humain a fourni la direction et le « pourquoi », tandis que l'IA a géré le travail de force pour chercher à travers des millions de possibilités afin de trouver le « comment ».

En fin de compte, ce papier est une victoire petite mais précise. Il montre que même dans un domaine aussi ancien que la multiplication de matrices, il reste de petites efficacités cachées à découvrir si l'on regarde de près. C'est comme trouver un nouveau chemin, légèrement plus court, à travers une forêt familière. Vous arrivez toujours au même endroit, mais vous y arrivez avec juste un pas de moins.

Résumé technique : 55 additions suffisent pour la multiplication de matrices 3 × 3 de rang 23

Énoncé du problème
Le document traite du problème de la minimisation de la complexité additive (le nombre d'additions et de soustractions) requise pour multiplier deux matrices $3 \times 3$ arbitraires sur un anneau associatif, étant donné un rang multiplicatif fixé à 23. Alors que l'algorithme de Strassen a établi que la multiplication de matrices peut être accélérée en réduisant les produits bilinéaires, le rang multiplicatif pour les matrices $3 \times 3$ générales est resté à 23 depuis la découverte de Laderman en 1976. La recherche récente s'est concentrée sur la réduction du nombre d'additions scalaires nécessaires pour réaliser ces schémas de rang 23. Avant ce travail, l'état de l'art était de 56 additions, réalisé par Sun.

Méthodologie
Les auteurs construisent un nouvel algorithme en optimisant les étapes linéaires d'une factorisation de tenseur préexistante. La méthodologie procède comme suit :

Tenseur de base : La construction utilise la factorisation cr58_cn122 de Perminov, publiée publiquement, qui nécessitait initialement 58 additions (14 pour l'entrée gauche, 15 pour l'entrée droite et 29 pour la reconstruction de la sortie).
Synthèse exacte des applications de facteurs : Les auteurs effectuent une recherche de dépendance exhaustive au sein du modèle de programme linéaire direct (SLP) d'addition/soustraction binaire pour optimiser les trois applications linéaires ( $U, V, W$ $U, V, W$ ) qui transforment les 9 entrées de la matrice en 23 formes bilinéaires.
- Ils identifient que pour l'orientation fixée du tenseur, le nombre minimal de portes nécessaires pour générer les directions de sortie requises dépasse la borne inférieure théorique basée sur les directions distinctes non-bases ( $d(F)$ ).
- Plus précisément, ils prouvent que pour le facteur gauche ( $U$ ), le coût est de 13 (un de plus que le plancher de 12) ; pour le facteur droit ( $V$ ), le coût est de 14 (un de plus que le plancher de 13) ; et pour le facteur de sortie ( $W$ ), le coût est de 14 (un de plus que le plancher de 13).
Principe de transposition : Pour obtenir le circuit de reconstruction de la sortie (qui mappe 23 produits vers 9 entrées de matrice), les auteurs transposent le circuit d'optimisation à 14 additions pour $W$ . En utilisant le principe de transposition de circuit linéaire, un circuit avec $L$ portes, $n$ entrées et $m$ sorties se transforme en un circuit pour la transposée avec $L + m - n$ portes. L'application de cela au circuit $W$ ( $L=14, n=9, m=23$ ) produit un circuit de sortie de 28 portes.
Vérification : La correction de l'algorithme est vérifiée en contrôlant les 729 identités de Brent sur les entiers $\mathbb{Z}$ . Les auteurs fournissent quatre méthodes de vérification indépendantes, incluant des implémentations Python et Node.js, garantissant que le résultat est valable sur tout anneau associatif (commutatif ou non) puisque l'alphabet des coefficients est restreint à $\{-1, 0, 1\}$ .

Contributions clés

Nouvelle borne supérieure : Le document présente une réalisation de la multiplication de matrices $3 \times 3$ utilisant 23 multiplications scalaires et 55 additions/soustractions, améliorant le record précédent de 56.
Certificat d'optimalité : Les auteurs fournissent un circuit linéaire prouvablement optimal pour l'orientation spécifique du tenseur utilisée. Ils démontrent que pour le tenseur fixe cr58_cn122, la somme des coûts des étapes linéaires ne peut être inférieure à 55 dans le modèle standard de SLP bilinéaire à trois étapes.
Publication exacte des données : Le document inclut le programme linéaire direct complet, les facteurs du tenseur et un « certificat gelé » qui permet une régénération octet par octet et une vérification indépendante des 729 identités.

Résultats
L'anatomie du circuit résultant est la suivante :

Prétraitement gauche (A) : 13 additions (mappage de 9 entrées vers 23 formes).
Prétraitement droit (B) : 14 additions (mappage de 9 entrées vers 23 formes).
Couche bilinéaire : 23 multiplications.
Reconstruction de sortie : 28 additions (mappage de 23 produits vers 9 sorties).
Travail linéaire total : 55 additions.

Le document confirme que l'algorithme s'applique à tout anneau associatif car les coefficients sont dans $\{-1, 0, 1\}$ et l'ordre des produits bilinéaires est préservé.

Signification et affirmations
Les auteurs déclarent explicitement qu'ils ne prétendent pas que 55 est le minimum global parmi toutes les décompositions de rang 23 possibles, ni qu'il est optimal dans les modèles de circuits permettant d'autres opérations primitives que l'addition/soustraction. Cependant, dans le modèle spécifique d'une orientation de tenseur fixée et du programme linéaire direct bilinéaire standard à trois étapes, 55 est le plus petit nombre d'additions actuellement connu.

La signification de ce travail réside dans :

Amélioration incrémentale : Il abaisse la borne supérieure d'une addition, poursuivant la tendance de l'optimisation de la complexité additive pour des rangs multiplicatifs fixes.
Vérification rigoureuse : Le résultat est soutenu par une arithmétique entière exacte et des implémentations multiples indépendantes, évitant le recours à des tests numériques ou aléatoires.
Découverte assistée par IA : Le document révèle que la découverte a été pilotée par une investigation dirigée par l'humain utilisant des agents IA (OpenAI GPT-5.6 Sol et Codex) pour la recherche, la synthèse et la vérification. Le chercheur humain a défini les objectifs et les critères d'acceptation, tandis que les agents IA ont exécuté les recherches de circuits et généré le certificat. Les auteurs soulignent que la validité mathématique repose entièrement sur les 729 identités exactes et le programme linéaire direct imprimé, et non sur l'implication de l'IA.

La nouvelle danse qui bat des records

Pourquoi cela importe (et pourquoi cela n'importe pas)

L'IA derrière le rideau

Résumé technique : 55 additions suffisent pour la multiplication de matrices 3 × 3 de rang 23

Articles similaires