Algorithme de Strassen

En mathématiques, plus précisément en algèbre linéaire, l’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n, proposé par Volker Strassen en 1969^[1]. La complexité de l'algorithme est en O ( n 2 , 807 ) {\displaystyle O(n^{2,807})} , avec pour la première fois un exposant inférieur à celui de la multiplication naïve qui est en O ( n 3 ) {\displaystyle O(n^{3})} . Par contre, il a l'inconvénient de ne pas être stable numériquement^[2].

L'algorithme de Strassen est le premier algorithme de multiplication de matrices n × n {\displaystyle n\times n} demandant asymptotiquement un nombre d'opérations arithmétiques (additions et multiplications) inférieur à O ( n 3 ) {\displaystyle O(n^{3})} . Ce n'est cependant pas le premier algorithme « plus rapide » que l'algorithme naïf : Shmuel Winograd avait donné en 1967^{[réf. nécessaire]} un algorithme demandant environ n 3 / 2 {\displaystyle n^{3}/2} multiplications dans le cas de matrices à coefficients dans un anneau commutatif, contre n 3 {\displaystyle n^{3}} environ pour l'algorithme naïf ; mais on ignorait s'il était possible de multiplier des matrices en complexité sous-cubique.

De surcroît, l'article de Strassen montre comment utiliser l'algorithme rapide de multiplication pour calculer l'inverse d'une matrice avec la même borne de complexité. Il prouve ainsi que l'algorithme usuel du pivot de Gauss n'est pas optimal.

Le travail de Strassen a ouvert un champ de recherche important en informatique théorique. La question centrale dans ce domaine est de savoir s'il est possible de multiplier deux matrices n × n {\displaystyle n\times n} en O ( n ω ) {\displaystyle O(n^{\omega })} opérations pour ω {\displaystyle \omega } arbitrairement proche de  2 {\displaystyle 2} . Parmi les résultats importants qui suivront, on peut citer notamment l'algorithme de Coppersmith-Winograd (1987), dont la complexité O ( n 2 , 376 ) {\displaystyle O(n^{2,376})} est longtemps restée la meilleure connue.

Soit R un anneau unitaire et soient A et B des matrices carrées de taille n dont les coefficients sont éléments de l'ensemble sous-jacent à R. Pour des raisons de simplicité, on traite le cas où n est une puissance de 2. On peut toujours se ramener à ce cas en rajoutant éventuellement des colonnes et des lignes de zéros. L'algorithme de Strassen permet de calculer la matrice produit C.

Les trois matrices A, B et C sont divisées en matrices par blocs de taille égale :

A = [ A 1 , 1 A 1 , 2 A 2 , 1 A 2 , 2 ]  ,  B = [ B 1 , 1 B 1 , 2 B 2 , 1 B 2 , 2 ]  ,  C = [ C 1 , 1 C 1 , 2 C 2 , 1 C 2 , 2 ] {\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}}

où

A i , j , B i , j , C i , j ∈ R n / 2 × R n / 2 . {\displaystyle \mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{n/2}\times R^{n/2}.}

On a alors

C 1 , 1 = A 1 , 1 B 1 , 1 + A 1 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}}

C 1 , 2 = A 1 , 1 B 1 , 2 + A 1 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}}

C 2 , 1 = A 2 , 1 B 1 , 1 + A 2 , 2 B 2 , 1 {\displaystyle \mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}}

C 2 , 2 = A 2 , 1 B 1 , 2 + A 2 , 2 B 2 , 2 {\displaystyle \mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}}

Cette méthode nécessite 8 multiplications de matrices pour calculer les C_i,j, comme dans le produit classique.

La force de l'algorithme de Strassen réside dans un ensemble de sept nouvelles matrices M_i qui vont servir à exprimer les C_i,j avec seulement 7 multiplications au lieu de 8 :

M 1 := ( A 1 , 1 + A 2 , 2 ) ( B 1 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})}

M 2 := ( A 2 , 1 + A 2 , 2 ) B 1 , 1 {\displaystyle \mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}}

M 3 := A 1 , 1 ( B 1 , 2 − B 2 , 2 ) {\displaystyle \mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})}

M 4 := A 2 , 2 ( B 2 , 1 − B 1 , 1 ) {\displaystyle \mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})}

M 5 := ( A 1 , 1 + A 1 , 2 ) B 2 , 2 {\displaystyle \mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}}

M 6 := ( A 2 , 1 − A 1 , 1 ) ( B 1 , 1 + B 1 , 2 ) {\displaystyle \mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}

M 7 := ( A 1 , 2 − A 2 , 2 ) ( B 2 , 1 + B 2 , 2 ) {\displaystyle \mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})}

Les C_i,j sont alors exprimées comme

C 1 , 1 = M 1 + M 4 − M 5 + M 7 {\displaystyle \mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}}

C 1 , 2 = M 3 + M 5 {\displaystyle \mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}}

C 2 , 1 = M 2 + M 4 {\displaystyle \mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}}

C 2 , 2 = M 1 − M 2 + M 3 + M 6 {\displaystyle \mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}}

Le procédé est reproduit récursivement jusqu'à ce que les matrices A et B soient « de petite taille ».

Il n'est pas nécessaire d'itérer le procédé jusqu'à une taille 1. En pratique, l'algorithme de Strassen est utilisé pour les matrices de grande taille. Il divise la taille jusqu'aux dizaines ou centaines et un autre algorithme de multiplication prend ensuite le relais pour calculer le produit des « petites matrices » obtenues.

Dans l'algorithme original de Strassen, chaque niveau de récursion effectue 18 additions et soustractions de blocs en plus des 7 multiplications. En 1970, Shmuel Winograd propose des formules alternatives qui nécessitent le même nombre de multiplications mais seulement 15 additions. En 2010, Marco Bodrato donne une nouvelle variante avec, pour un produit quelconque, toujours 7 multiplications et 15 additions comme dans l'algorithme de Winograd, mais avec moins d'opérations dans le cas particulier du calcul du carré d'une matrice.

La multiplication matricielle « naïve » utilise

n 3 = n log 2 ⁡ 8 {\displaystyle n^{3}=n^{\log _{2}8}}

multiplications des éléments de l'anneau R. Les additions sont généralement ignorées dans le calcul de la complexité car elles sont beaucoup plus rapides que la multiplication, en particulier si la taille des entrées est supérieure à la taille du mot machine.

Avec l'algorithme de Strassen, le nombre de multiplications T(n) est réduit à

n log 2 ⁡ ( 7 ) ≈ n 2,807 . {\displaystyle n^{\log _{2}(7)}\approx n^{2{,}807}.}

Cet exposant est obtenu comme la solution, par le Master theorem, de l'équation par récurrence

T ( n ) = 7 T ( n / 2 ) + Θ ( n 2 ) . {\displaystyle T(n)=7\,T(n/2)+\Theta (n^{2}).}

La constante dans la complexité est de l'ordre de 6 même si ce chiffre varie selon les implémentations et la forme de la matrice initiale^[3]. Pour les matrices avec peu de coefficients non nuls (matrices creuses), l'algorithme de Strassen n'est pas algorithmiquement efficace.

(en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill, 2001, 2^e éd. [détail de l’édition], chap. 31, section 31.2 (« Strassen's algorithm for matrix multiplication »), p. 739-745.

• (en) Eric W. Weisstein, « Strassen Formulas », sur MathWorld
• (en) Analyse de l'algorithme de Strassen à l'aide de Maple
• Gérard Sookahet, Algorithme de V. Strassen pour la multiplication rapide de matrices

• Portail de l’algèbre
• Portail de l'informatique théorique