Un algorithme rapide se paie deux fois
Il coûte des multiplications, et il coûte des additions, et les deux se comptent par des questions différentes. tensor-rank-toolkit répond exactement aux deux sur les applications assez petites pour être tranchées, où exactement veut dire démontré et non trouvé : un rang refermé des deux côtés, et un nombre de coefficients non nuls qui est le plus petit que tout changement de base puisse laisser.
Deux coûts, et non un seul
Un algorithme pour une application bilinéaire, ce sont trois opérateurs : L et R qui encodent les deux opérandes, P qui recombine les produits. Ses multiplications sont le rang de l'application, c'est-à-dire ce que compte une décomposition du tenseur. Ses additions sont fixées par le nombre de coefficients non nuls que portent ces trois opérateurs, ce que le décompte des multiplications ne voit jamais. Les deux sont minimisés ici, par des mathématiques différentes, et ils sont rapportés comme deux nombres plutôt que repliés en un seul. Sources : README.md, what-it-computes.md.
Ce qui fait d'un nombre, ici, un fait
Rien dans la bibliothèque n'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. La voie du solveur écrit ses réfutations en DRAT et les fait vérifier par drat-trim, si bien qu'une borne inférieure venue d'un solveur est vérifiable et non pas crue sur parole, et les théorèmes sur lesquels reposent ces voies sont énoncés et démontrés dans article/bilinear-rank.pdf. Chaque décompte que le dépôt sait redériver est redérivé depuis les binaires construits à chaque poussée, par reproduce/measure.py --check. Les quelques-uns qu'il ne sait pas redériver sont nommés un par un, avec ce que chacun coûterait à relancer, dans reproduce/questions.py : un nombre reporté dit ainsi sur sa propre ligne que rien ne le redérive.
Les multiplications, et une application tranchée à 13
Multiplier deux polynômes à 5 coefficients sur GF(2) demande 25 multiplications de façon naïve, et la descente bon marché ramène cela à 14. Neuf, dix et onze produits sont ensuite refusés par rank_lower_bound avant que la recherche n'ouvre le moindre nœud. Douze est écarté par exhaustion, 146 402 553 nœuds parcourus jusqu'au bout de l'arbre. lower-the-bound exhibe alors un treize en 80 nœuds. Le plancher et le plafond se rejoignent : le rang vaut donc exactement 13, et les deux moitiés en sont désormais démontrées à l'intérieur du dépôt. Barbulescu, Detrey, Estibals et Zimmermann ont publié ce même 13 en 2012, et rien ici ne les dépasse ; ce qui a changé, c'est que la ligne ne repose plus sur le fait qu'ils l'aient rapporté. Sources : descent_search/results.json, descent_search/what-the-exact-search-decides.md, incumbent_search/what-it-reaches.md.
descent_search/what-the-exact-search-decides.md et incumbent_search/what-it-reaches.md.Les additions, et 221 non-nuls ramenés à un 128 démontré
L'autre coût est fixé par les opérateurs. Étant donné U, la question est de savoir quel changement de base inversible V laisse à U V le moins de coefficients non nuls. Les deux opérateurs d'encodage de Strassen passent de 12 non-nuls à 10, et un opérateur en base alternative de 21 à 10, ce qui ramène les 18 additions de Strassen à 12 et le coefficient dominant de 7·N^log₂7 − 6·N² de 7 à 5. Dix n'est pas le meilleur résultat trouvé mais le plus petit que tout changement de base puisse laisser : choisir la base la plus creuse d'un sous-espace est un problème de matroïde, et un algorithme glouton y rend une base de poids minimal. Sur les trois opérateurs d'encodage d'un schéma ⟨3,3,3⟩ de rang 23 déjà publié, cela fait 221 non-nuls à 128, en un tiers de seconde environ, et 128 est là encore le minimum démontré plutôt que le meilleur résultat trouvé. Chaque coefficient que gardent ces trois matrices vaut 0, +1 ou −1 : le décompte ne cache donc aucune multiplication, un coefficient hors de cet alphabet en coûtant une par-dessus son addition, et il n'y en a aucun. Sources : matrix_sparsification/README.md, matrix_sparsification/what-it-is-worth.md.
matrix_sparsification/results.json.Un opérateur ⟨4,4,4⟩ est hors de portée de toute énumération, à quatorze millions de sous-ensembles de colonnes au poids six, et se traite en ne cherchant pas : un programme linéaire par coordonnée, en rationnels exacts, qui atteint une base vérifiée à 100 non-nuls en un tiers de seconde. Cette voie rend une borne supérieure et non une preuve, et elle atteint tout de même le minimum démontré sur chaque opérateur où une preuve existe, entre quatre et quinze fois plus vite que la recherche qui le démontre. Pourquoi il en va ainsi reste une question ouverte, puisque le théorème qui l'avait suggérée ne s'applique à aucun des opérateurs mesurés. Source : matrix_sparsification/method/answering-without-searching.md.
Et moins de non-nuls, ce n'est pas moins d'additions. Confiez la sortie de l'étape exacte à une passe qui repère les sous-expressions communes : un schéma brut s'améliore de 23 %, deux schémas déjà travaillés de 2 % et 7 %, et un opérateur sur neuf part dans le mauvais sens, six zéros de plus y coûtant deux additions. Une base de poids minimal n'est pas une base qui partage le plus de sous-expressions : l'approximation est donc mesurée plutôt que supposée, et les deux décomptes sont rapportés séparément. Le record publié donne la taille de cet écart : évalués naïvement, ces 128 coefficients répartis sur 55 lignes coûtent 73 additions, là où Karunaratne et Idamekorala donnent un circuit à 55 additions pour un tenseur ⟨3,3,3⟩ de rang 23 (arXiv:2607.28676, 2026), sur l'alphabet 0, +1, −1 et démontré optimal pour cette orientation. Les deux ne comptent pas la même chose, l'un un circuit qui partage des sous-expressions en base standard, l'autre un nombre de coefficients non nuls sous un changement de base : aucun des deux n'est donc un score contre l'autre. Sources : matrix_sparsification/measured-with-other-tools/before-a-subexpression-pass.md, matrix_sparsification/what-it-is-worth.md.
Les deux moitiés, dans un navigateur
Une décomposition n'est pas le livrable ; l'algorithme l'est. La recherche de rang retrouve les trois opérateurs depuis la décomposition qu'elle trouve et les écrit, et c'est à cela que sert la sparsification : minimise-rank fixtures/f2_5x5.tensor --emit-operators out fait passer 25 multiplications à 14, puis sparsify-operator out_L.sms fait passer cet opérateur de 31 non-nuls à 27. Moins de multiplications, puis moins d'additions, depuis une seule application, en deux commandes.
Les deux mêmes s'enchaînent dans cet ordre depuis un navigateur, sous la forme du flux décomposer-puis-rendre-creux de la console : une pression, quatre exécutions, chacune une exécution ordinaire avec sa propre commande, sa propre fiche et son propre code de sortie. Douze des treize outils y figurent, chacun énonçant ce qu'il demande, et la commande est montrée avant d'être lancée puis de nouveau à côté de la réponse, sous la forme d'une ligne que l'on peut retaper dans un terminal. Elle écoute sur l'adresse de bouclage, donc seule cette machine peut l'atteindre, et elle n'a besoin que de la bibliothèque standard de Python 3, c'est-à-dire exactement de ce qu'il fallait pour construire la boîte à outils. Source : web_interface/README.md.
Ce qui est démontré, et ce qui ne l'est pas
Chaque preuve ici est une exhaustion sur une application et à une taille, ou un minimum sur un opérateur. Le problème du rang bilinéaire lui-même reste ouvert, aucune borne supérieure de cette page ne démontre quoi que ce soit à elle seule, et l'arithmétique exacte rend une réponse digne de confiance, pas optimale. La descente ne démontre rien du tout : ce qu'elle rend est une décomposition, non une affirmation sur le rang véritable. Les temps sont de l'autre espèce, mesurés sur un seul cœur d'un i5-12450H, meilleur de trois exécutions sur une machine au repos, et valent comme ordre de grandeur et non comme chiffre : aucun test n'en assertit un et l'intégration continue n'en vérifie aucun, car un exécuteur partagé rendrait indiscernables une vraie régression et un après-midi chargé. Les décomptes sont exacts, assertis par la suite de tests, et rejoués à chaque poussée. Protocole : MEASURING.md.