Algorithme de Strassen

Algorithme de Strassen

L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969[1]. La complexité de l'algorithme est en O(n2,807), soit une meilleure complexité que la multiplication naïve (en O(n3)) mais moins bonne que celle de l'algorithme de Coppersmith-Winograd (en O(n2,376)).

Sommaire

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 naïve et donc le 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 l'anneau 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 :

\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ù

\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{n/2}\times F^{n/2}.

On a alors

\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}
\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}
\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}
\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 Ci,j, comme dans le produit classique.

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

\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})
\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}
\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})
\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})
\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}
\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})
\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})

Les Ci,j sont alors exprimées comme

\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}
\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}
\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}
\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}

Le procédé est répété jusqu'à ce que les matrices A et B soient « de petite taille »[2].

Complexité

La multiplication matricielle « naïve » utilise

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}\approx n^{2.807}.

Cet exposant est obtenu comme la solution de l'équation par récurrence

T(n) = 7T(n / 2) + Θ(n2).

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 stable numériquement.

Référence

  1. ↑ Strassen, Volker, Gaussian Elimination is not Optimal, Numerische Mathematik, 13:354-356, 1969
  2. ↑ 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.
  • 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–745.

Liens externes

v · Naïf  · Strassen  · Coppersmith-Winograd
Produit d'entiers Naïf  · Karatsuba  · Toom-Cook  · Schönhage-Strassen  · Fürer

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Strassen de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme De Strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme de strassen — L’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n. Il est dû à Volker Strassen en 1969.[1] La complexité de l algorithme est en O(n2,807), soit une meilleure complexité que la multiplication… …   Wikipédia en Français

  • Algorithme De Coppersmith-Winograd — L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en fait l algorithme le plus efficace… …   Wikipédia en Français

  • Algorithme de Coppersmith–Winograd — Algorithme de Coppersmith Winograd L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en… …   Wikipédia en Français

  • Algorithme de coppersmith-winograd — L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n du à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en fait l algorithme le plus efficace… …   Wikipédia en Français

  • Algorithme de Coppersmith-Winograd — L’algorithme de Coppersmith Winograd est un algorithme de calcul du produit de deux matrices carrées de taille n dû à Don Coppersmith et Shmuel Winograd en 1987[1]. Sa complexité algorithmique est en ce qui en fait l algorithme actuel le plus… …   Wikipédia en Français

  • Strassen — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Strassen peut désigner : Strassen, une commune autrichienne du district de Lienz dans le Tyrol ; Strassen, une commune luxembourgeoise du… …   Wikipédia en Français

  • Algorithme De Multiplication — Les techniques de multiplication permettent de calculer le résultat d une multiplication. Graphiquement, il s agit de transformer un rectangle multiplicateur × multiplicande en une ligne, en conservant le nombre d éléments. Exemples: Sommaire 1… …   Wikipédia en Français

  • Algorithme De Karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

  • Algorithme de karatsuba — L algorithme de Karatsuba (1960) est une méthode permettant de multiplier rapidement deux nombres avec une complexité en au lieu de O(n2) pour la méthode naïve. Note : . Sommaire 1 Énoncé …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”