Algorithme de Strassen pour la multiplication matricielle

envisager de multiplier deux matrices 2x2, comme suit:

A B * E F = AE+BG AF+BH
C D   G H   CE+DG CF+DH

la façon évidente de calculer le côté droit est juste de faire les 8 multiples et 4 additions. Mais imaginez que les multiplications soient beaucoup plus coûteuses que les additions, donc nous voulons réduire le nombre de multiplications si possible. Strassen utilise un truc pour calculer le côté droit avec une multiplication en moins et beaucoup plus d'additions (et quelques soustractions).

Voici les 7 multiples:

M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH

donc pour calculer AE+BG, commencez avec M1+M7 (ce qui nous donne les Termes AE et BG), puis ajoutez/soustrayez certains des autres Ms jusqu'à ce que AE+BG soit tout ce qu'il nous reste. Miraculeusement, les M sont choisis de sorte que M1+M7-M2+M5 fonctionne. Même avec les 3 autres résultats requis.

maintenant, il suffit de réaliser que cela fonctionne non seulement pour les matrices 2x2, mais pour toutes les matrices (Pair) dimensionné où le A..H sont submatrices.

à mon avis, il y a 3 idées que vous devez obtenir:

1. Vous pouvez fractionner une matrice en blocs et fonctionner sur la matrice de blocs comme vous le feriez sur une matrice de nombres. En particulier, vous pouvez multiplier deux de ces matrices de bloc (bien sûr aussi longtemps que le nombre de lignes de bloc dans l'une correspond au nombre de colonnes de bloc dans l'autre) et obtenir le même résultat que vous obtiendriez en multipliant les matrices originales de nombres.

2. les blocs nécessaires pour exprimer le résultat de la multiplication matricielle par blocs de 2x2 ont suffisamment de facteurs communs pour permettre de les calculer en moins de multiplications que la formule originale implique. C'est l'astuce décrite dans la réponse de Tony .

3. récursion.

algorithme de Strassen est juste une application de la ci-dessus. Pour comprendre l' analyse de sa complexité, vous devez lire " mathématiques concrètes " par Ronald Graham, Donald Knuth, Oren Patashnik ou un livre similaire.

a jeté un rapide coup d'oeil sur Wikipedia et il me semble que cet algorithme est une légère réduction du nombre de multiplications nécessaires en réarrangeant les équations.

voici une analogie. Combien de multiplications dans x*x + 5*x + 6 ? De deux, non? Combien de multiplications dans (x+2)(x+3) ? L'un, à droite? Mais ils sont de la même expression!

Note, Je ne m'attends pas à ce que cela fournisse une compréhension profonde de l'algorithme, juste une manière intuitive dans lequel vous pouvez comprendre comment l'algorithme peut éventuellement conduire à une amélioration dans le calcul de la complexité.