Complexité de la multiplication de matrices

L'approche la plus simple pour calculer le produit de deux matrices ${\displaystyle A}$ et ${\displaystyle B}$ d'ordre ${\displaystyle 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 ${\displaystyle n^{3}}$ multiplications et ${\displaystyle n^{3}-n^{2}}$ additions scalaires pour calculer le produit de deux matrices carrées d'ordre ${\displaystyle n}$. Sa complexité de calcul est ${\displaystyle O(n^{3})}$ 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).

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 ${\displaystyle n}$ comme des matrices à entrées en blocs de taille 2, la multiplication des matrices de taille ${\displaystyle n}$ peut être réduite à 7 sous-problèmes de multiplication des matrices de taille ${\displaystyle n/2}$. L'application récursive de cette démarche donne un algorithme nécessitant ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2,807})}$ 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[5], mais la multiplication est plus rapide pour ${\displaystyle n>100}$ [6] et l'algorithme figure dans plusieurs bibliothèques de programmes, telles que BLAS[7]. Les algorithmes de multiplication matricielle rapide ne peuvent pas atteindre la « stabilité par composant , mais certains peuvent afficher une « stabilité par norme »[8]. 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.

Henry Cohn, Robert Kleinberg, Balázs Szegedy et Chris Umans[21] - [22] 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 propriété du triple produit (en) (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[23]. 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 (en)[24].

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

L'exposant ${\displaystyle \omega }$ 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 ${\displaystyle O(n^{\omega })}$ opérations : il y au moins un facteur supplémentaire en ${\displaystyle n^{o(1)}}$[13].

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

Comme la sortie du problème de multiplication matricielle est de taille ${\displaystyle n^{2}}$, on a ${\displaystyle \omega (k)\geq 2}$ pour toutes les valeurs de ${\displaystyle k}$. Si l'on peut prouver pour certaines valeurs de ${\displaystyle k}$ entre 0 et 1 que ${\displaystyle \omega (k)\leq 2}$, alors un tel résultat montre que ${\displaystyle \omega (k)=2}$ pour ces ${\displaystyle k}$. Le plus grand k tel que ${\displaystyle \omega (k)=2}$ est connu sous le nom d' « exposant dual de multiplication de matrices », généralement noté α . α est appelé le « dual » car montrer que ${\displaystyle \alpha =1}$ équivaut à montrer que ${\displaystyle \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[27].

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

Dans son article de 1969, où il prouve la complexité ${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$ 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 ${\displaystyle O(n^{\omega })}$ pour certains ${\displaystyle \omega \geq 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 ${\displaystyle (2n,2n)}$ peut être partitionnée en quatre blocs de taille ${\displaystyle (n,n)}$ :

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$

Sous cette forme, son inverse est

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{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{bmatrix}},}$

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

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

${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n)}$.

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

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}}$

et pour ${\displaystyle M(n)\leq cn^{\omega }}$, et ${\displaystyle \alpha =2^{\omega }\geq 4}$, on obtient finalement

${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\leq d(2^{k})^{\omega }\end{aligned}}}$

pour une constante d. 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 A est inversible, l'égalité

${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$

définit une décomposition LU par blocs qui peut être appliquée récursivement à ${\displaystyle A}$ et à ${\displaystyle D-CA^{-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

${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B)}$.

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 ${\displaystyle n^{3}}$ multiplications ; ainsi des matrices de taille 4 dans ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$ peuvent être multipliées en 47 multiplications[29] ; des matrices de taille 3 sur un anneau commutatif, peuvent être multipliées en 21 multiplications [30] - [31] - [32] (23 si l'anneau n'est pas commutatif [33]). La borne inférieure des multiplications nécessaires est ${\displaystyle 2mn+2n-m-2}$ (multiplication d'une matrice ${\displaystyle (n,m)}$ par une matrice ${\displaystyle (m,n)}$, avec ${\displaystyle m\geq n\geq 3}$), ce qui signifie que le cas ${\displaystyle n=3}$ nécessite au moins 19 multiplications et le cas ${\displaystyle n=4}$ au moins 34[34]. Pour ${\displaystyle n=2}$, les 7 multiplications et 15 additions sont minimales, contre seulement 4 additions avec 8 multiplications[35] - [36] - [37].