Algorithme de Strassen 1231655 31385515 2008-07-07T19:47:58Z 86.212.231.230 /* Liens externes */ L’'''algorithme de Strassen''' est un [[Algorithmique|algorithme]] calculant le [[Produit matriciel|produit]] de deux [[Matrice (mathématiques)|matrice]]s carrées de taille ''n''. Il est dû à [[Volker Strassen]] en [[1969]].<ref>Strassen, Volker, ''Gaussian Elimination is not Optimal'', Numerische Mathematik, 13:354-356, 1969</ref> La [[Complexité algorithmique|complexité]] de l'algorithme est en <math>O(n^{2,807})</math>, soit une meilleure complexité que la multiplication naïve (en <math>O(n^3)</math>) mais moins bonne que celle de l'[[algorithme de Coppersmith-Winograd]] (en <math>O(n^{2,376})</math>). == Importance du résultat == L'algorithme de Strassen a été publié en [[1969]]. Non seulement il améliore la complexité connue du produit matriciel mais il démontre de surcroît que la multiplication naive et donc le [[Élimination de Gauss-Jordan|pivot de Gauss]] ne sont pas optimaux. Le travail de Strassen a permis de développer un nouveau champ de la recherche en informatique théorique : le calcul rapide du produit matriciel. Plusieurs résultats importants suivront : [[Shmuel Winograd]] publie un algorithme en 1980 qui utilise moins d'additions que celui de Strassen et surtout en [[1987]], [[Don Coppersmith]] et Winograd publient l'[[algorithme de Coppersmith-Winograd]] améliorant la complexité de la multiplication. == Description de l'algorithme == Soient ''A'' et ''B'' deux matrices carrées de taille ''n'' dont les entrées sont sur le [[Corps (mathématiques)|corps]] ''F''. 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 [[Matrice par blocs|matrices par blocs]] de taille égale : :<math> \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} </math> où :<math>\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{n/2}\times F^{n/2}.</math> On a alors :<math>\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} </math> :<math>\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} </math> :<math>\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} </math> :<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </math> Cette méthode nécessite 8 multiplications de matrices pour calculer les ''C<sub>i,j</sub>'', comme dans le produit classique. La force de l'algorithme de Strassen réside dans un ensemble de sept nouvelles matrices ''M<sub>i</sub>'' qui vont servir à exprimer les ''C''<sub>i,j</sub> avec seulement 7 multiplications au lieu de 8 : :<math>\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})</math> :<math>\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math> :<math>\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math> :<math>\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math> :<math>\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math> :<math>\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})</math> :<math>\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})</math> Les ''C''<sub>i,j</sub> sont alors exprimées comme :<math>\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}</math> :<math>\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}</math> :<math>\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}</math> :<math>\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}</math> Le procédé est répété jusqu'à ce que les matrices ''A'' et ''B'' soient « de petite taille ».<ref>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 relai pour calculer le produit des « petites matrices » obtenues.</ref> == Complexité == La multiplication matricielle « naïve » utilise :<math>n^3 = n^{\log_{2}8}</math> multiplications des éléments du corps ''F''. 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 à :<math>n^{\log_{2}7}\approx n^{2.807}.</math> Cet exposant est obtenu comme la solution de l'équation par [[récurrence]] :<math>T(n)=7T(n/2)+\Theta(n^2).</math> La constante dans la complexité est de l'ordre de 50, ce qui fait que l'algorithme de Strassen n'est efficace que pour des matrices de grandes tailles. L'algorithme de Strassen est aussi peu efficace algorithmiquement sur les matrices avec peu de coefficients non-nuls (matrices creuses). L'avantage algorithmique sur le nombre de multiplications a néanmoins un inconvénient : l'algorithme n'est pas très [[Stabilité numérique|stable numériquement]]. == Référence == <references/> * [[Thomas Cormen]], [[Charles Leiserson]], and [[Ronald Rivest]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-07-013143-0. Chapter 31: Section 31.2: Strassen's algorithm for matrix multiplication, pp.739&ndash;745. == Liens externes == * {{en}} [http://mathworld.wolfram.com/StrassenFormulas.html MathWorld : formules de Strassen] * {{en}} [http://bl-uits-tucson.ads.iu.edu/tom/strassen/ Analyse de l'algorithme de Strassen à l'aide de] [[Maple]] * {{fr}} Gérard Sookahet, [http://gersoo.free.fr/docs/stras/stras.html Algorithme de V. Strassen pour la multiplication rapide de matrices] {{Portail|mathématiques|informatique}} [[Catégorie:Algorithme|Strassen]] [[Catégorie:Matrice]] [[bg:Алгоритъм на Щрасен]] [[cs:Strassenův algoritmus]] [[de:Strassen-Algorithmus]] [[en:Strassen algorithm]] [[id:Algoritma Strassen]] [[it:Algoritmo di Strassen]] [[ja:Strassenのアルゴリズム]] [[ko:슈트라센 알고리즘]] [[pt:Algoritmo de Strassen]] [[ru:Алгоритм Штрассена]] [[zh:Strassen演算法]]