Un algorithme non-commutatif pour multiplier des matrices 4×4 en utilisant 48 multiplications non-complexes

Informations fondamentales

• ID de l'article: 2506.13242
• Titre: A non-commutative algorithm for multiplying 4×4 matrices using 48 non-complex multiplications
• Auteurs: Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic
• Institutions: Univ. Grenoble Alpes (Dumas & Pernet), Univ. Lille (Sedoglavic)
• Classification: cs.SC (Calcul symbolique)
• Date de publication: 27 novembre 2025 (prépublication arXiv)
• Lien de l'article: https://arxiv.org/abs/2506.13242

Résumé

Cet article propose un algorithme non-commutatif utilisant 48 multiplications scalaires pour calculer la multiplication de matrices 4×4, en utilisant uniquement des coefficients rationnels, sans nombres complexes. Il s'agit d'une amélioration de l'algorithme en domaine complexe proposé par AlphaEvolve11, obtenue par projection vers le domaine rationnel via des transformations isotropes (isotropy). L'article fournit également une implémentation en programme linéaire (straight-line program) et présente une variante de base alternative réalisant une complexité opératoire de $7n^{2+\frac{\log_2 3}{2}} + o(n^{2+\frac{\log_2 3}{2}})$ sur tout anneau contenant l'inverse de 2.

Contexte et motivation de la recherche

Contexte du problème

1. Problème central: Rechercher des algorithmes non-commutatifs optimaux pour la multiplication de matrices de petites dimensions, en particulier réduire le nombre de multiplications scalaires requises. La multiplication matricielle est une opération fondamentale en informatique et en calcul numérique, dont l'efficacité affecte directement les performances de nombreuses applications.
2. Importance:
   • La complexité temporelle de la multiplication matricielle affecte directement l'efficacité du calcul d'algèbre linéaire, de l'apprentissage automatique, du calcul scientifique et d'autres domaines
   • L'algorithme de Strassen (1969) a d'abord réduit la complexité de $O(n^3)$ à $O(n^{2.81})$, ouvrant la recherche sur la multiplication matricielle rapide
   • Les algorithmes de multiplication matricielle de petites dimensions peuvent être appliqués récursivement à des matrices plus grandes, ce qui a une valeur d'application pratique
3. Limitations des méthodes existantes:
   • L'algorithme de Strassen nécessite 49 multiplications sur des matrices 4×4 (deux niveaux de récursion)
   • Fawzi et al. 5 ont réalisé 47 multiplications sur des corps de caractéristique 2
   • AlphaEvolve11 a trouvé un algorithme avec 48 multiplications en utilisant des modèles de langage de grande taille et des agents de codage évolutifs, mais nécessite des coefficients complexes
   • Les coefficients complexes limitent l'application de l'algorithme sur certains anneaux (comme l'anneau des entiers, les corps finis)
4. Motivation de la recherche:
   • Éliminer l'exigence de nombres complexes pour rendre l'algorithme applicable à des structures algébriques plus larges
   • Utiliser les symétries de la théorie de la décomposition tensorielle (actions du groupe d'isotropie) pour transformer systématiquement l'algorithme
   • Fournir une implémentation pratique en programme linéaire, optimisant les termes constants

Contributions principales

1. Contribution théorique majeure: Prouver l'existence de points rationnels dans l'orbite d'isotropie de l'algorithme AlphaEvolve, proposer un algorithme avec coefficients purement rationnels utilisant 48 multiplications
2. Contribution méthodologique: Appliquer systématiquement la théorie du groupe d'isotropie de la décomposition tensorielle, projeter l'algorithme du domaine complexe vers le domaine rationnel via des transformations isotropes (Équation 24)
3. Contributions pratiques:
   • Fournir une implémentation complète en programme linéaire (Listings 1-4), totalisant 341 opérations
   • Borne théorique de complexité: $11.65625n^{2.792} - 10.65625n^2$
   • Fournir une variante de base alternative nécessitant seulement 6 opérations (1+2+3), avec complexité $7n^{2.792}$
4. Généralité: L'algorithme s'applique à tout anneau contenant l'inverse de 2, élargissant la portée des applications
5. Implémentation open-source: Toutes les matrices et codes sont disponibles publiquement dans la bibliothèque PLinOpt

Détails de la méthode

Définition de la tâche

Entrée: Deux matrices 4×4 $A = (a_{ij})$ et $B = (b_{ij})$, avec éléments d'un anneau $R$ contenant $\frac{1}{2}$
Sortie: Matrice produit $C = A \cdot B = (c_{ij})$
Contrainte: Minimiser le nombre de multiplications scalaires, en utilisant uniquement des coefficients rationnels (éviter les nombres complexes)

Cadre théorique: représentation de la décomposition tensorielle

1. Représentation tensorielle des applications bilinéaires

La multiplication matricielle peut être représentée comme une application bilinéaire: $\beta_{mm}: R^{m \times k} \times R^{k \times n} \rightarrow R^{m \times n}, \quad (A, B) \mapsto A \cdot B$

Cette application est codée comme une décomposition tensorielle dans l'espace tensoriel $(R^{m \times k})^* \otimes (R^{k \times n})^* \otimes R^{m \times n}$: $T = \sum_{i=1}^r M_i \otimes N_i \otimes O_i$

où:

• $r$ est le rang tensoriel (tensor rank), correspondant au nombre de multiplications scalaires requises
• Chaque $(M_i, N_i, O_i)$ est un tenseur de rang un
• Représentation trilinéaire: $\text{Trace}(O_i^T \cdot M_i \cdot N_i)$

2. Représentation tensorielle de l'algorithme de Strassen

L'algorithme de Strassen pour la multiplication de matrices 2×2 (7 multiplications) correspond à une décomposition de rang tensoriel 7, de type $X^2Y^2Z^2 + 6XYZ$.

3. Action du groupe d'isotropie (Isotropy Group Action)

Théorème 2.1: Le groupe d'isotropie du tenseur de multiplication matricielle est: $\text{psl}_{\pm}(R^m) \times \text{psl}_{\pm}(R^k) \times \text{psl}_{\pm}(R^n) \rtimes S_3$

Définition 2.2: L'action d'une isotropie $g = (U \times V \times W)$ sur un tenseur de rang un $A \otimes B \otimes C$ est: $(U^{-T} \cdot A \cdot V^T) \otimes (V^{-T} \cdot B \cdot W^T) \otimes (W^{-T} \cdot C \cdot U^T)$

Cela préserve le rang tensoriel mais modifie les coefficients.

Construction de l'algorithme principal

Transformation isotrope clé

L'innovation centrale de cet article est de trouver une transformation isotrope spécifique (Équation 24): $\begin{bmatrix} I & 0 & 0 & I \\ 0 & 1 & I & 0 \\ 0 & -I & -1 & 0 \\ -1 & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} I & 0 & 0 & 1 \\ 0 & -I & -I & 0 \\ 0 & -I & I & 0 \\ -I & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

où $I$ est l'unité imaginaire.

Décomposition tensorielle à coefficients rationnels

Après application de l'isotropie ci-dessus, on obtient une décomposition de 48 tenseurs de rang un (Équations 25-72), chacun de la forme: $m_i = \left(\sum_{j,k} \alpha_{jk}^{(i)} a_{jk}\right) \otimes \left(\sum_{j,k} \beta_{jk}^{(i)} b_{jk}\right) \otimes \left(\sum_{j,k} \gamma_{jk}^{(i)} c_{jk}\right)$

Caractéristiques clés:

• Tous les coefficients $\alpha, \beta, \gamma \in \{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$ (nombres rationnels)
• Type tensoriel: $16X^2Y^2Z^2 + 32XYZ$ (16 tenseurs de rang 2×2×2, 32 de rang 1×1×1)
• Les dénominateurs contiennent uniquement des puissances de 2, 4, 8

Exemple: premier terme de multiplication

$m_1 = \frac{1}{4}\left(\sum_{i,j} (-1)^{i+j+1} a_{ij}\right) \otimes (b_{31} + b_{41}) \otimes \left(\sum c_{terms}\right)$

Représentation matricielle LRP

L'algorithme peut être représenté de manière compacte par trois matrices $(L, R, P)$:

• $L \in R^{48 \times 16}$: transformation linéaire des éléments de $A$ vers les 48 opérandes gauches
• $R \in R^{48 \times 16}$: transformation linéaire des éléments de $B$ vers les 48 opérandes droits
• $P \in R^{16 \times 48}$: transformation linéaire des 48 produits vers les éléments de $C$

Flux de calcul: $\text{vec}(C) = P \cdot (L \cdot \text{vec}(A) \odot R \cdot \text{vec}(B))$

où $\odot$ désigne la multiplication élément par élément (produit de Hadamard).

Points techniques innovants

1. Utilisation systématique des symétries: Plutôt que par recherche par essais et erreurs, trouver la transformation isotrope en utilisant le sous-groupe stabilisateur $(C_2 \times D_4) \rtimes C_2$ et des conjectures guidées par la théorie
2. Projection des nombres complexes aux nombres rationnels: Prouver que l'algorithme trouvé dans l'espace complexe de haute dimension peut être projeté dans un sous-espace rationnel, ce qui est un résultat non trivial
3. Optimisation du programme linéaire:
   • Utiliser l'outil PLinOpt pour générer automatiquement des programmes linéaires optimisés
   • Réduire le nombre d'opérations via la décomposition du noyau (kernel decomposition)
   • Même si les coefficients de la matrice $R$ sont simples, le programme linéaire optimal peut nécessiter des multiplications non triviales
4. Méthode de base alternative: Simplifier davantage par changement de base (change of basis), réduisant les opérations à 336 (comparé aux 341 originaux)

Configuration expérimentale

Outils d'implémentation

• Bibliothèque PLinOpt: Ensemble de routines C++ traitant l'optimisation de programmes linéaires et bilinéaires
• Taille du code: Environ 8.09 kSLOC (milliers de lignes de code source)
• Open-source: Toutes les matrices et codes sont disponibles publiquement sur GitHub

Fichiers de données

Les différentes représentations de l'algorithme sont stockées comme:

• 4x4x4_48_rational_L.sms, _R.sms, _P.sms: représentation LRP standard
• 4x4x4_48_rational-ALT_*.sms: représentation de base alternative
• 4x4x4_48_rational-CoB_*.sms: matrices de changement de base

Métriques d'évaluation

1. Rang tensoriel: Nombre de multiplications scalaires requises (48)
2. Nombre total d'opérations: Nombre total d'additions et d'opérations de décalage
3. Complexité asymptotique: $O(n^{\log_4 3}) \approx O(n^{2.792})$
4. Terme constant: Coefficient constant dominant et coefficients de termes d'ordre inférieur

Résultats expérimentaux

Résultats principaux

Programme linéaire standard (Listings 1-4)

Décomposition des opérations:

• Matrice $L$: 104 additions
• Matrice $R$: 84 additions + 1 multiplication (décalage binaire)
• Matrice $P$: 119 additions + 33 multiplications (décalage binaire)
• Total: 341 opérations

Borne de complexité: $\left(1 + \frac{341}{48-16}\right)n^{2+\log_4 3} - \frac{341}{32}n^2 \approx 11.65625n^{2.792} - 10.65625n^2$

Variante de base alternative (Appendice C)

Décomposition des opérations:

• $L_{alt}$: 1 addition
• $R_{alt}$: 2 additions
• $P_{alt}$: 3 additions
• Total: 6 opérations

Coût du changement de base:

• CoB_L: 103 additions
• CoB_R: 79 additions + 5 multiplications
• CoB_P: 116 additions + 33 multiplications
• Total: 336 opérations

Borne de complexité: $7n^{2.792} + \frac{336}{31}(n^{\log_4 47} - n^2) = 7n^{2.792} + o(n^{2.792})$

Comparaison avec les méthodes existantes

Découvertes clés

1. Preuve d'existence: Prouver que dans l'orbite d'isotropie de l'algorithme AlphaEvolve existe effectivement un point rationnel, ce qui n'est pas évident
2. Simplicité des coefficients: Tous les coefficients sont dans $\{-1, -\frac{1}{2}, 0, \frac{1}{2}, 1\}$, faciles à implémenter
3. Paradoxe d'optimisation: Bien que les coefficients de la matrice $R$ soient uniquement dans $\{-1, 0, 1\}$, le programme linéaire optimal nécessite toujours des multiplications non triviales (en raison de la décomposition du noyau)
4. Avantage de la base alternative: Via le changement de base, on peut réduire la constante dominante de 11.66 à 7.00, au prix d'un coût de changement de base de $o(n^{2.792})$

Travaux connexes

Historique de la multiplication matricielle rapide

1. Strassen (1969): Premier algorithme $O(n^{2.81})$, 7 multiplications pour matrices 2×2
2. de Groote (1978): Étude du groupe d'isotropie et des algorithmes optimaux en géométrie algébrique
3. Théorème 2.2: Prouver que tous les algorithmes 2×2 à 7 multiplications forment une orbite unique

Progrès récents

1. Fawzi et al. (2022) 5: Utiliser l'apprentissage par renforcement pour découvrir un algorithme à 47 multiplications en caractéristique 2
2. Kaporin (2024) 8: Utiliser les moindres carrés non linéaires pour résoudre les équations de Brent en nombres complexes
3. AlphaEvolve (2025) 11: Utiliser des modèles de langage de grande taille et des agents évolutifs pour découvrir un algorithme à 48 multiplications (complexe) et 63 multiplications (3×4×7)

Recherche sur la stabilité numérique

• Dumas et al. (2024) 2: Étudier la précision numérique de l'algorithme de Strassen, découvrir qu'il n'est pas numériquement optimal
• L'analyse numérique de l'algorithme de cet article reste à faire

Avantages de cet article

1. Rigueur théorique: Basé sur la théorie du groupe d'isotropie, plutôt que sur une recherche purement heuristique
2. Généralité: Les coefficients rationnels rendent l'algorithme applicable à des structures algébriques plus larges
3. Reproductibilité: Représentation matricielle complète et implémentation open-source

Conclusion et discussion

Conclusions principales

1. Convertir avec succès l'algorithme complexe d'AlphaEvolve en algorithme rationnel, en conservant 48 multiplications
2. L'action du groupe d'isotropie est un outil efficace pour explorer systématiquement l'espace des algorithmes
3. Fournir deux implémentations: version standard (341 opérations) et version base alternative (6+336 opérations)
4. L'algorithme s'applique à tout anneau contenant $\frac{1}{2}$, élargissant la portée des applications

Limitations

1. Restriction de l'anneau: Nécessite que 2 soit inversible, non applicable aux corps de caractéristique 2
2. Terme constant important: La constante 11.66 de la version standard est importante, l'avantage n'apparaît que pour des matrices suffisamment grandes
3. Stabilité numérique inconnue: Aucune analyse de précision numérique comme dans 2 n'a été effectuée
4. Non-constructif: La découverte de la transformation isotrope repose toujours sur des "conjectures éclairées", pas complètement automatisée

Directions futures

1. Algorithme 3×4×7: L'article jumeau 3 traite un autre algorithme complexe d'AlphaEvolve
2. Analyse numérique: Étudier la propagation d'erreurs et le nombre de condition de cet algorithme
3. Découverte automatisée: Développer des méthodes systématiques pour rechercher automatiquement les transformations isotropes
4. Autres dimensions: Appliquer la même méthode aux cas 5×5, 3×3×3, etc.
5. Performance pratique: Tester les performances sur du matériel réel, en considérant le cache, le parallélisme, etc.

Évaluation approfondie

Avantages

1. Contribution théorique significative

• Combler une lacune importante: Résoudre la limitation des coefficients complexes de l'algorithme AlphaEvolve, un problème pratique réel
• Innovation méthodologique: Application systématique de la théorie du groupe d'isotropie, fournissant un chemin théorique des nombres complexes aux nombres rationnels
• Rigueur mathématique: Basé sur la théorie de la géométrie tensorielle de Landsberg, avec des fondations algébriques solides

2. Valeur pratique élevée

• Implémentation complète: Fournir des programmes linéaires et des matrices LRP, directement utilisables
• Reproductibilité open-source: Tous les données et codes sont disponibles publiquement dans la bibliothèque PLinOpt
• Large applicabilité: Les coefficients rationnels permettent l'utilisation de l'algorithme sur les entiers, les rationnels, les corps finis (caractéristique impaire), etc.

3. Détails techniques suffisants

• Présentation complète de l'algorithme: Les équations 25-72 énumèrent en détail les 48 termes de multiplication
• Représentations multiples: Fournir des formes trilinéaires, des matrices LRP, des programmes linéaires et d'autres représentations
• Stratégies d'optimisation: Démontrer des techniques d'optimisation telles que la décomposition du noyau et la base alternative

4. Écriture claire

• Introduction suffisante du contexte: Introduction progressive de l'algorithme de Strassen à la théorie de la décomposition tensorielle
• Exemples riches: L'exemple 2.1 montre comment l'isotropie introduit les nombres complexes
• Notation systématisée: Définitions claires, notation cohérente

Insuffisances

1. Limitations de la méthode

• Découverte de la transformation isotrope: Reconnaître l'utilisation de "conjectures éclairées", manque de méthode de recherche systématisée
• Dépendance du sous-groupe stabilisateur: Nécessiter de connaître le sous-groupe stabilisateur $(C_2 \times D_4) \rtimes C_2$, peut être difficile à obtenir pour de nouveaux problèmes
• Restriction de caractéristique: Non applicable aux corps de caractéristique 2 (l'algorithme de Fawzi à 47 multiplications est au contraire applicable)

2. Analyse expérimentale insuffisante

• Absence de tests de performance réelle: Pas de test du temps d'exécution sur du matériel réel
• Pas d'analyse de stabilité numérique: Reconnaître que c'est un travail futur, mais très important pour les applications pratiques
• Comparaison des termes constants: Pas de comparaison quantitative des termes constants avec d'autres algorithmes

3. Profondeur théorique

• Preuve d'existence incomplète: Montrer seulement un point rationnel, sans prouver son unicité ou optimalité
• Structure d'orbite non explorée: Les questions sur la position, le nombre de points rationnels dans l'orbite, etc., ne sont pas discutées
• Bornes inférieures non abordées: Ne pas discuter de la borne inférieure théorique pour la multiplication de matrices 4×4 (est-il possible d'avoir <48?)

4. Détails d'expression

• Notation complexe: De nombreux indices et notations tensorielles peuvent être peu accessibles aux non-spécialistes
• Lisibilité du code: Les programmes linéaires (Listings 1-4) manquent de commentaires
• Présentation matricielle: Les grandes matrices de l'Appendice B sont difficiles à comprendre directement dans leur structure

Impact

Contribution au domaine

1. Pont entre théorie et pratique: Convertir l'algorithme découvert par l'IA en forme mathématiquement utilisable
2. Démonstration méthodologique: Montrer l'application pratique de la théorie du groupe d'isotropie dans l'optimisation d'algorithmes
3. Inspiration pour la recherche ultérieure: Fournir un modèle pour traiter d'autres algorithmes complexes découverts par l'IA

Valeur pratique

1. Modérée: En raison du terme constant important (11.66), l'avantage n'apparaît que pour les matrices à grande échelle (comme $n > 100$)
2. Domaines spécifiques: Valeur plus élevée dans les systèmes de calcul symbolique nécessitant des calculs rationnels exacts
3. Valeur pédagogique: Excellent cas d'étude pour l'application de la décomposition tensorielle et de la théorie du groupe d'isotropie

Reproductibilité

• Excellente: Matrices complètes, codes et chaîne d'outils publiquement disponibles
• Facilité d'utilisation: La bibliothèque PLinOpt fournit des outils pour générer automatiquement des programmes linéaires
• Documentation complète: L'Appendice énumère en détail les emplacements de tous les fichiers de données

Scénarios d'application

Scénarios d'application idéaux

1. Systèmes de calcul symbolique: Comme Maple, Mathematica pour les opérations matricielles exactes
2. Calcul sur corps finis: Algèbre linéaire sur corps finis de caractéristique impaire
3. Matrices à grande échelle: Application récursive à des matrices $n \geq 128$
4. Recherche théorique: Comme outil pour étudier les algorithmes rapides et le rang tensoriel

Scénarios non applicables

1. Petites matrices: Pour une seule matrice 4×4, l'algorithme naïf (64 multiplications) peut être plus rapide en raison d'un terme constant plus petit
2. Calcul en virgule flottante: Stabilité numérique inconnue, peut être moins performant que les algorithmes traditionnels
3. Corps de caractéristique 2: L'algorithme de Fawzi à 47 multiplications est supérieur
4. Accélération matérielle: La multiplication matricielle optimisée par GPU moderne peut être plus rapide

Références

Citations clés

1. 13 Strassen (1969): "Gaussian elimination is not optimal" - Travail fondateur de la multiplication matricielle rapide
2. 6,7 de Groote (1978): Articles originaux de la théorie du groupe d'isotropie
3. 11 Novikov et al. (2025): AlphaEvolve - Algorithme complexe original amélioré dans cet article
4. 10 Landsberg (2016): "Geometry and complexity theory" - Fondations théoriques
5. 2 Dumas et al. (2024): Analyse de précision numérique de l'algorithme de Strassen

Travaux connexes

• 5 Fawzi et al. (2022): Algorithme à 47 multiplications découvert par apprentissage par renforcement (caractéristique 2)
• 9 Karstadt & Schwartz (2017): Autres optimisations de multiplication matricielle
• 4 Dumas et al. (2025): Méthodes pour générer automatiquement des algorithmes exacts rapides
• 3 Dumas et al. (2025): Algorithme de matrices 3×4×7 à 63 multiplications (article jumeau)

Évaluation globale

Ceci est un article de haute qualité en informatique théorique, convertissant avec succès l'algorithme du domaine complexe découvert par l'IA en algorithme du domaine rationnel, avec une importance théorique significative et une certaine valeur pratique. Les principaux avantages de l'article sont:

1. Résoudre un problème pratique: La limitation des coefficients complexes d'AlphaEvolve restreint la portée des applications
2. Méthode rigoureuse: Basée sur la théorie mature de la décomposition tensorielle et du groupe d'isotropie
3. Implémentation complète: Fournir une implémentation open-source reproductible

Les principales insuffisances sont:

1. La découverte de la transformation isotrope nécessite toujours des conjectures manuelles
2. Manque d'analyse de performance réelle et de stabilité numérique
3. Le terme constant important limite la praticité

Indice de recommandation: ⭐⭐⭐⭐ (4/5)
Recommandé pour les chercheurs intéressés par le calcul symbolique, la décomposition tensorielle et les algorithmes rapides. Pour les applications pratiques, il est nécessaire d'évaluer selon des scénarios spécifiques si cet algorithme est supérieur aux méthodes traditionnelles.