Complexité de la multiplication de matrices

En informatique théorique, la complexité de la multiplication de matrices est le nombre d'opérations requises pour l'opération de produit matriciel. Les algorithmes de multiplication de matrices constituent un sujet central dans les algorithmes théoriques et numériques en algèbre linéaire numérique et en optimisation, donc déterminer la complexité en temps du produit est d'une importance pratique.

L'application directe de la définition mathématique de la multiplication de matrices donne un algorithme qui nécessite $\mathrm{\Theta }\left(n^3\right)$ opérations sur le corps de base pour multiplier deux matrices d'ordre $n$. Il existe des algorithmes qui demandent moins d'opérations que le simple « algorithme naïf ». Le premier de ces algorithmes est l'algorithme de Strassen, conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide ». Le nombre minimal d'opérations du corps de base nécessaires pour multiplier deux matrices carrées d'ordre $n$ est encore inconnu en 2023. Il s'agit là d'une question ouverte majeure en informatique théorique. Toutefois, ce nombre est au moins d'ordre $n^2$.

En octobre 2022, la meilleure complexité en temps de multiplication de matrices est $O\left(n^{2,37188}\right)$, valeur annoncée par Ran Duan, Hongxun Wu et Renfei Zhou dans une prépublication. Cette borne améliore la borne de $O\left(n^{2,3728596}\right)$ donnée par Josh Alman et Virginia Vassilevska WilliamsModèle:,. Depuis, l'exposant a été réduit à $2,371552$ puis en 2025 à $2,371339$. Cependant, cette amélioration et d'autres améliorations similaires de l'algorithme de Strassen ne sont pas utilisées en pratique, car elles sont des « algorithmes galactiques » en ce sens que la constante du $O$ est si élevée qu'ils ne sont utiles que pour les matrices trop grandes pour être traitées par les ordinateurs actuels.

Algorithmes simples

Modèle:Article détaillé Si $A$ et $B$ sont deux matrices d'ordre $n$ sur un anneau, leur produit $AB$ est aussi une matrice d'ordre $n$ sur cet anneau, dont les entrées sont :

$(AB{)}_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}$.

Algorithme élémentaire

L'approche la plus simple pour calculer le produit de deux matrices $A$ et $B$ d'ordre $n$ consiste à évaluer les expressions arithmétiques issues de la définition de la multiplication matricielle.

Cet algorithme nécessite, dans le pire des cas $n^3$ multiplications et $n^3-n^2$ additions scalaires pour calculer le produit de deux matrices carrées d'ordre $n$. Sa complexité de calcul est $O\left(n^3\right)$ dans un modèle de calcul où les opérations élémentaires d'addition et de multiplication prennent un temps constant (en pratique, c'est le cas pour les nombres en virgule flottante, mais pas nécessairement pour les entiers).

Algorithme de Strassen

L'algorithme de Strassen améliore la multiplication matricielle naïve grâce à une approche diviser pour régner.

L'observation clé est que la multiplication de deux matrices de taille 2 peut être effectuée avec seulement 7 multiplications, au lieu des 8 habituelles, au prix de 11 opérations d'addition et de soustraction supplémentaires. Ainsi, en traitant les matrices de taille $n$ comme des matrices à entrées en blocs de taille 2, la multiplication des matrices de taille $n$ peut être réduite à 7 sous-problèmes de multiplication des matrices de taille $n/2$. L'application récursive de cette démarche donne un algorithme nécessitant $O\left(n^{{\log }_{2}7}\right)\approx O\left(n^{2,807}\right)$ opérations scalaires.

Contrairement aux algorithmes qui ont une complexité asymptotique meilleure, l'algorithme de Strassen est utilisable et utilisé dans la pratique. La stabilité numérique est moins bonne que pour l'algorithme naïf, mais la multiplication est plus rapide pour $n>100$ et l'algorithme figure dans plusieurs bibliothèques de programmes, telles que BLAS. Les algorithmes de multiplication matricielle rapide ne peuvent pas atteindre la « stabilité par composant, mais certains peuvent afficher une « stabilité par norme ». L'algorithme est utile pour les grandes matrices sur des domaines exacts tels que les corps finis, où la stabilité numérique ne pose pas de problème.

Exposant de la multiplication matricielle

Amélioration successives des estimations de l'exposant $\omega$ de la complexité de calcul de la multiplication matricielle $O\left(n^{\omega }\right)$.

Chronologie de l'exposant de multiplication matricielle

Année	Oméga	Auteurs
1969	2,8074	Strassen
1978	2,796	Pan
1979	2,780	Bini, Capovani, Romani, Lotti
1981	2,522	Schönhage
1981	2,517	Romani
1981	2,496	Coppersmith, Winograd
1986	2,479	Strassen
1990	2,3755	Coppersmith, Winograd
2010	2,3737	Stothers
2013	2.3729	WilliamsModèle:,
2014	2.3728639	Le Gall
2020	2.3728596	Alman, Williams
2022	2.371866	Duan, Wu, Zhou
2025	2.371339	Alman, Duan, Williams, Y. Xu, Z. Xu, Zhou

L'exposant de la multiplication matricielle, généralement noté Modèle:Formule, est le plus petit nombre réel pour lequel deux matrices de taille $n$ sur un corps peuvent être multipliées en utilisant $n^{\omega +o(1)}$ opérations élémentaires.

La borne inférieure naïve et la multiplication élémentaire de matrices donnent l'encadrement 2 ≤ Modèle:Formule ≤ 3. Il existe une série d'algorithmes de multiplication matricielle pour améliorer ces bornes sur Modèle:Formule.

Avant l'algorithme de Duan, Wu et Zhou, la meilleure borne sur Modèle:Formule était Modèle:Formule, due à Josh Alman et Virginia Vassilevska Williams. Cet algorithme, comme tous les autres algorithmes récents dans cette direction de recherche, utilise une méthode dite méthode laser, qui est une généralisation de l'algorithme donné par Don Coppersmith et Shmuel Winograd en 1990 et qui était le meilleur algorithme de multiplication matricielle jusqu'en 2010. L'idée fondamentale de ces algorithmes est similaire à l'algorithme de Strassen : c'est une méthode pour multiplier deux matrices Modèle:Formule avec moins de Modèle:Formule multiplications, et qui applique la technique de manière récursive. La méthode laser a des limites sur l'exposant et ne peut pas être utilisée pour montrer que Modèle:Formule. Duan, Wu et Zhou identifient une source d'amélioration dans la méthode laser appelée « perte de combinaison ». Ils l'exploitent dans une variante de la méthode laser qu'ils utilisent pour montrer Modèle:Formule, améliorant ainsi la barrière de la méthode laser conventionnelle. Avec cette nouvelle approche, une autre limite s'applique selon Duan, Wu et Zhou et qui montre qu'à son tour la valeur Modèle:Formule ne peut être franchie uniquement en traitant la perte de combinaison dans la méthode laser.

Algorithmes de multiplication matricielle et théorie des groupes

Henry Cohn, Robert Kleinberg, Balázs Szegedy et Chris UmansModèle:, placent les méthodes telles que les algorithmes de Strassen et de Coppersmith–Winograd dans le contexte entièrement différent de théorie des groupes, en utilisant des triplets de sous-ensembles de groupes finis qui satisfont une propriété de disjonction appelée la Modèle:Lien (abrégée en PTP). Ils énoncent également un ensemble de conjectures qui, si elles sont vraies, impliqueraient qu'il existe des algorithmes de multiplication matricielle avec une complexité essentiellement quadratique. Cela démontrerait que l'exposant optimal de la multiplication matricielle est 2, ce qui est effectivement conjecturé. Une de ces conjectures est que les familles de produits en couronne de groupes abéliens avec des groupes symétriques réalisent des familles de triplets de sous-ensembles avec une version simultanée du PTP. Plusieurs de leurs conjectures ont depuis été réfutées par Blasiak, Cohn, Church, Grochow, Naslund, Sawin et Umans en utilisant la méthode dite du Slice Rank. De plus, Alon, Shpilka et Chris Umans ont montré que certaines de ces conjectures impliquant l'existence d'une multiplication matricielle rapide sont incompatibles avec une autre conjecture plausible, la conjecture du tournesol.

Bornes inférieures pour ω

Il existe une borne inférieure triviale pour Modèle:Formule, à savoir Modèle:Formule ≥ 2. Étant donné que tout algorithme de multiplication de deux matrices de taille $n$ doit traiter toutes les $2n^2$ entrées, il existe une borne inférieure asymptotique triviale d'opérations $\mathrm{\Omega }\left(n^2\right)$ pour tout algorithme de multiplication de matrices. On ne sait pas si Modèle:Formule > 2. Une borne inférieure est $\mathrm{\Omega }\left(n^2\right)\log n$, et concerne les circuits arithmétiques à coefficients bornés sur les nombres réels ou complexes, et elle est due à Ran Raz.

L'exposant Modèle:Formule est un point d'accumulation, en ce sens qu'il est le minimum de l'exposant, pris sur tout algorithme de multiplication matricielle. On sait que ce point d'accumulation n'est pas atteint. En d'autres termes, dans le modèle de calcul usuel, il n'y a pas d'algorithme de multiplication matricielle qui utilise exactement $O\left(n^{\omega }\right)$ opérations : il y au moins un facteur supplémentaire en $n^{o(1)}$.

Multiplication de matrices rectangulaires

Des techniques similaires s'appliquent à la multiplication de matrices rectangulaires. L'objet d'étude central est $\omega (k)$, qui est le plus petit exposant $c$ tel que l'on peut multiplier une matrice de taille $n\times \lceil n^k\rceil$ avec une matrice de taille $\lceil n^k\rceil \times n$ en $O\left(n^{c+o(1)}\right)$ opérations arithmétiques. Un résultat en complexité algébrique montre que la multiplication des matrices de taille $n\times \lceil n^k\rceil$ et $\lceil n^k\rceil \times n$ nécessite le même nombre d'opérations arithmétiques que la multiplication de matrices de taille $n\times \lceil n^k\rceil$ et $n\times n$ et de taille $n\times n$ et $n\times \lceil n^k\rceil$, de sorte que cela englobe la complexité de la multiplication matricielle rectangulaire. Cela généralise l'exposant de multiplication de matrice carrée, puisque $\omega (1)=\omega$.

Comme la sortie du problème de multiplication matricielle est de taille $n^2$, on a $\omega (k)\ge 2$ pour toutes les valeurs de $k$. Si l'on peut prouver pour certaines valeurs de $k$ entre 0 et 1 que $\omega (k)\le 2$, alors un tel résultat montre que $\omega (k)=2$ pour ces $k$. Le plus grand k tel que $\omega (k)=2$ est connu sous le nom d'« exposant dual de multiplication de matrices », généralement noté $\alpha$ ; il est appelé le « dual » car montrer que $\alpha =1$ équivaut à montrer que $\omega =2$. Comme l'exposant de multiplication matricielle, l'exposant dual de multiplication matricielle apparaît parfois dans la complexité des algorithmes d'algèbre linéaire numérique et d'optimisation.

La première borne sur $\alpha$ est celle de Coppersmith en 1982, qui a montré que $\alpha >0,17227$ . La meilleure borne connue sur $\alpha$ est $\alpha >0,31389$, donnée par Le Gall et Urrutia. Cet article contient également des bornes sur $\omega (k)$.

Problèmes connexes

Les problèmes qui ont la même complexité asymptotique que la multiplication matricielle comprennent le déterminant, l'inversion matricielle, l'élimination gaussienne. Les problèmes dont la complexité s'exprime en termes de $\omega$ comprennent le polynôme caractéristique, les valeurs propres (mais pas les vecteurs propres).

Inversion de matrice, déterminant et élimination gaussienne

Dans son article de 1969, où il prouve la complexité $O\left(n^{{\log }_{2}7}\right)\approx O\left(n^{2.807}\right)$ pour le calcul matriciel, Strassen a également prouvé que l'inversion matricielle, le calcul du déterminant et l'élimination gaussienne ont, à une constante multiplicative près, la même complexité de calcul que la multiplication matricielle. La preuve ne fait aucune hypothèse sur la multiplication matricielle utilisée, sauf que sa complexité est $O\left(n^{\omega }\right)$ pour certains $\omega$ ≥ 2.

Le point de départ de la preuve de Strassen utilise la multiplication matricielle par blocs. Plus précisément, une matrice de dimension paire $(2n,2n)$ peut être partitionnée en quatre blocs de taille $(n,n)$ :

$\left[\begin{array}{cc}A& B\\ C& D\end{array}\right].$

Sous cette forme, son inverse est

${\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]}^{-1}=\left[\begin{array}{cc}{A}^{-1}+A^{-1}B(D-{CA}^{-1}B{)}^{-1}{CA}^{-1}& -A^{-1}B(D-{CA}^{-1}B{)}^{-1}\\ -(D-{CA}^{-1}B{)}^{-1}{CA}^{-1}& (D-{CA}^{-1}B{)}^{-1}\end{array}\right],$

pourvu que $A$ et son complément de Schur $D-{CA}^{-1}B$ soient inversibles.

Ainsi, l'inverse d'une matrice de taille $(2n,2n)$ peut être calculée avec deux inversions, six multiplications et quatre additions ou inverses additifs de matrices $(n,n)$. En notant respectivement $I(n)$, $M(n)$ et $A(n)=n^2$ le nombre d'opérations nécessaires pour inverser, multiplier et additionner de matrices de taille $n$, on obtient

$I(2n)\le 2I(n)+6M(n)+4A(n)$.

Pour $n=2^k$ on peut appliquer cette formule récursivement,

$\begin{array}{cc}I(2^k)& \le 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\ & \le 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\ & ⋮\end{array}$

et pour $M(n)\le c{n}^{\omega }$, et $\alpha =2^{\omega }\ge 4$, on obtient finalement

$\begin{array}{cc}I(2^k)& \le 2^{k}I(1)+6c({\alpha }^{k-1}+2{\alpha }^{k-2}+\cdots +2^{k-1}{\alpha }^0)+k{2}^{k+1}\\ & \le 2^k+6c\frac{{\alpha }^k-2^k}{\alpha -2}+k{2}^{k+1}\le d{\left(2^k\right)}^{\omega }\end{array}$

pour une constante Modèle:Mvar. Ceci prouve la complexité annoncée pour les matrices telles que toutes les sous-matrices qui doivent être inversées sont inversibles. Cette complexité est donc prouvée pour presque toutes les matrices, car une matrice avec des entrées choisies au hasard est inversible avec probabilité 1.

Le même argument s'applique à la décomposition LU, car, si la matrice Modèle:Mvar est inversible, l'égalité

$\left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\left[\begin{array}{cc}I& 0\\ C{A}^{-1}& I\end{array}\right]\left[\begin{array}{cc}A& B\\ 0& D-C{A}^{-1}B\end{array}\right]$

définit une décomposition LU par blocs qui peut être appliquée récursivement à $A$ et à $D-C{A}^{-1}B,$ pour obtenir finalement une décomposition LU de la matrice d'origine.

L'argument s'applique également au déterminant, puisqu'il résulte de la décomposition LU par blocs que

$\det \left[\begin{array}{cc}A& B\\ C& D\end{array}\right]=\det (A)\det (D-C{A}^{-1}B)$.

Minimiser le nombre d'opérations

Le problème de la minimisation du nombre d'opérations arithmétiques est lié à la minimisation du nombre de multiplications, qui est généralement une opération plus coûteuse que l'addition, mais ces algorithmes ne sont pas pratiques, notamment pour des petites matrices. On peut améliorer la méthode usuelle en $n^3$ multiplications ; ainsi des matrices de taille 4 dans $\mathbb{Z}/2\mathbb{Z}$ peuvent être multipliées en 47 multiplications ; des matrices de taille 3 sur un anneau commutatif, peuvent être multipliées en 21 multiplications Modèle:,Modèle:, (23 si l'anneau n'est pas commutatif ). La borne inférieure des multiplications nécessaires est $2mn+2n-m-2$ (multiplication d'une matrice $(n,m)$ par une matrice $(m,n)$, avec $m\ge n\ge 3$), ce qui signifie que le cas $n=3$ nécessite au moins 19 multiplications et le cas $n=4$ au moins 34. Pour $n=2$, les 7 multiplications et 15 additions sont minimales, contre seulement 4 additions avec 8 multiplicationsModèle:,Modèle:,.

Articles liés

• Algorithme de Cocke-Younger-Kasami
• Algorithme de Freivalds, un simple algorithme de Monte-Carlo qui, étant donné les matrices Modèle:Mvar, Modèle:Mvar et Modèle:Mvar, vérifie en temps $\mathrm{\Theta }\left(n^2\right)$ si $AB=C$.
• Problème des multiplications matricielles enchaînées
• Produit matriciel, pour les définitions abstraites
• Matrice creuse.

Liens externes

• « Encore un autre catalogue d'algorithmes de multiplication matricielle rapide », sur Université de Lille.