Combien de multiplications un produit exige-t-il ?

Laboratoire Jean Kuntzmann, Université Grenoble Alpes
Encadré par Jean-Guillaume Dumas · 21 mai au 15 juillet 2024
tensor-rank-toolkit est un travail ultérieur et indépendant qui en est issu, en C++ sur Givaro, construit pour l'essentiel en 2026

D'où cela vient

Huit semaines au LJK, en Julia. La méthode est une descente gloutonne : elle prend une application bilinéaire sur un corps fini et la réécrit de façon répétée dans une base différente, à la recherche d'une famille génératrice comptant moins de composantes de rang 1 que celle dont elle est partie. La réécriture a le droit d'utiliser plus de composantes qu'au départ, puisqu'il lui suffit d'engendrer l'application d'origine : c'est ce que sont les cinq produits de Karatsuba pour un produit à quatre coefficients.

Elle a été refaite en C++ sur Givaro, la bibliothèque d'arithmétique exacte issue du même laboratoire. Rien n'y est jamais un flottant, de sorte qu'un rang rapporté est un fait portant sur l'application et non un artefact d'arrondi, et chaque décomposition est reconstruite et remultipliée contre l'application avant d'être affichée.

L'étape coûteuse de la descente est mal tarifée, et c'est le résultat que le stage a laissé derrière lui. L'étape 3 balaie le vivier complet des applications de rang un. Sur les quatre applications polynomiales, elle a amélioré la réponse dans deux cas sur quatre, d'un produit chacun, pour un coût compris entre 58 et 184 fois celui des deux premières étapes réunies. Toute suite qui ne ferait qu'accélérer l'étape 3 optimiserait la partie qui, le plus souvent, ne rapporte rien. Source : fixtures/README.md.

Ce que c'est devenu

Cette descente n'est qu'un volet sur dix. tensor-rank-toolkit attaque la même question par dix directions avec douze outils en ligne de commande, chacun répondant à une question qu'aucun autre ne traite : la descente bon marché, une recherche exhaustive qui rend une preuve, des bornes inférieures sans aucune recherche, un codage SAT dont les réfutations sont écrites en DRAT et revérifiées par drat-trim, un quotient par le groupe de symétries, une énumération sans isomorphes, et une forme canonique pour les tenseurs à deux tranches qui traite un faisceau 4×4 en une cinquantaine de microsecondes, en temps polynomial. Sources : README.md, OPTIONS/one-question-per-command.md, OPTIONS/reading-the-answer-off.md.

Le second volet du stage est ici un volet à part entière. Rendre creux les opérateurs, c'est le coût que le décompte des multiplications ignore : moins de coefficients non nuls signifie moins d'additions. Les deux opérateurs d'encodage de Strassen passent de 12 coefficients non nuls à 10 et un opérateur en base alternative de 21 à 10, en quelques millisecondes, ce qui ramène les 18 additions de Strassen à 12. L'article d'origine ne rapportait aucun résultat mesuré sur cet opérateur, seulement que son programme prenait trop de temps pour un problème simple. Source : matrix_sparsification/README.md.

Décidé, et non plus proposé

Une heuristique propose et ne démontre jamais : une décomposition est un témoin, et seule une réfutation fixe un rang. La recherche exhaustive, elle, réfute. Quatre applications sont désormais tranchées entièrement, en arithmétique exacte, chaque réponse étant reconstruite et remultipliée contre l'application qu'elle prétend calculer.

Les sept produits de Strassen et la preuve de Winograd que six sont impossibles, ni l'un ni l'autre supposés, tous deux recalculés depuis le tenseur, en 0,55 s au total. GF(16) est le cas coûteux, 38,8 minutes pour la seule réfutation ; celle de neuf pour F3 3×6 prend 7,65 s. Le 13 et le 10 sont les valeurs publiées par Barbulescu, Detrey, Estibals et Zimmermann en 2012 : rien ici ne les dépasse. Ce qui a changé, c'est que les deux moitiés sont désormais démontrées à l'intérieur du dépôt, au lieu que la moitié de chacune soit citée. Sources : famous_tensors/decided-exactly.md, what-it-computes.md, incumbent_search/what-it-reaches.md, state-of-the-art/what-is-missing.md.

Un cas montre à quoi servent les niveaux supplémentaires. La convolution cyclique de longueur 7 sur F2 reste à 15 après la descente, et la liste courte de son étape 3 est de 0 sur 16 129 : pas une seule application de rang un ne l'améliore strictement, si bien qu'un glouton à première amélioration n'a nulle part où aller. Couper le même arbre au meilleur candidat courant plutôt qu'à une cible atteint 13 en 22 nœuds, ce qui est le rang publié. Source : incumbent_search/what-it-reaches.md.

Face à l'état de l'art publié

L'« état de l'art » ne se gagne que contre le code de quelqu'un d'autre sur la même question : la référence est donc l'implémentation publique de yang2025, clonée hors de l'arborescence et exécutée sur cette machine. Même question, un seul cœur, multiplication de matrices 2×2 sur GF(2) : réfuter six produits coûte 0,954 s à leur Java et 30,45 s à leur Python, contre 0,0362 s ici, et 0,0013 s avec le quotient par les orbites. Le balayage complet est de 1,385 s contre 0,0554 s. Source : state-of-the-art/comparing-against-the-baseline.md.

Ce temps d'exécution est un résultat d'implémentation et ne doit pas se lire comme un résultat algorithmique. C'est du C++ contre du Java, et une feuille en bits compactés contre une feuille générale. Les deux recherches visitent 25 426 nœuds et 25 399, et deux programmes écrits indépendamment qui s'accordent d'aussi près sur la taille d'un arbre témoignent qu'il s'agit du même algorithme, ce que disent les deux articles. La différence algorithmique, c'est le quotient par les orbites : 648 nœuds, 39,2 fois moins, et celle-là survit à n'importe quel langage.

Un second volet confie la même question à un solveur SAT, et sur la seule instance où les deux ont été menés au bout, il l'emporte d'un ordre de grandeur : écarter huit produits pour la multiplication dans GF(16) coûte 2 328 s à l'arbre et 108,0 s à kissat, 21 fois moins. L'avantage croît avec l'instance, ce qui en fait l'intérêt : à égalité sur la multiplication de matrices 2×2, vingt et une fois sur GF(16). Source : satisfiability/measurements.md.

Là où c'est en retard

Deux valeurs publiées sont égalées, deux ne le sont pas. gf32_multiplication atteint 14 face à un mu_2(5) = 13 publié, et gf64_multiplication atteint 20 face à mu_2(6) = 15. Sur la multiplication de matrices 3×3×3, la marche sur plateau atteint 24 là où Laderman a publié 23 en 1976, et la recherche exhaustive n'atteint pas cette taille du tout : sa réfutation est projetée à une dizaine d'heures et n'a pas été lancée. Sources : fixtures/published-targets.md, famous_tensors/README.md.

La seule application véritablement ouverte ici est F2 4×7, encadrée par 15 ≤ rang ≤ 16 : la borne inférieure est celle de la littérature, la borne supérieure est celle de ce dépôt, et aucun des deux côtés ne l'a refermée. Source : state-of-the-art/where-we-stand.md.

Ce qui est ouvert, et la suite

yang2025 élague par sommes de rangs et par rref ; le quotient de covanov2019 retire des orbites entières. Ce sont des mécanismes différents, et rien ne montre qu'ils ne peuvent pas être combinés. Aucun article trouvé ne publie cette combinaison, et ce dépôt non plus : c'est une direction ouverte et non un résultat, et c'est celle que ce travail prendrait ensuite. Source : state-of-the-art/comparing-against-the-baseline.md.

Lire