Comment prouver que la multiplication matricielle de deux matrices 2x2 ne peut se faire en moins de 7 multiplications?

Dans la multiplication matricielle de Strassen, nous affirmons un fait étrange (du moins pour moi) que la multiplication matricielle de deux 2 x 2 prend 7 multiplications.

Question: Comment prouver qu'il est impossible de multiplier deux matrices 2 x 2 en 6 multiplications?

Veuillez noter que les matrices sont sur des entiers.

algorithms complexity-theory lower-bounds Complexité
la source

Il existe d'autres algorithmes de multiplication matricielle qui peuvent être plus rapides. Cet article Web d'une classe Stanford CME 323 fournit des détails sur l'algorithme de Strassen, la multiplication matricielle: l'algorithme de Strassen . Il existe un sujet Wikipédia, l' algorithme Strassen, qui rentre dans les détails et contient des liens vers des informations supplémentaires.

Richard Chambers,

@RichardChambers Notez que l'algorithme de Strassen a multiplications. Il me semble plausible que cette limite inférieure soit vraie.

7

$7$

Stella Biderman

La formulation de cette question est fausse. Il existe de nombreuses matrices qui peuvent être multipliées par multiplications. Vous voulez demander une preuve que, dans le pire des cas, il faut 7 aka il existe une matrice qui nécessite 7

6

$6$

Stella Biderman

@StellaBiderman oui j'ai vu que Strassen a 7 multiplications. Je n'ai pas regardé les autres, plus rapides et les algorithmes avec une complexité moindre. D'après ce que je peux dire, ils utilisent la même approche sous-matrice que celle de Strassen mais je ne suis pas sûr. J'ajoutais juste quelques informations supplémentaires sur Strassen spécifiquement.

Richard Chambers

Il semble qu'il manque quelque chose à votre question. Je peux facilement donner un algorithme qui peut multiplier au moins certaines matrices avec 0 multiplications. Il y a probablement une contrainte que vous ne mentionnez pas.

Jörg W Mittag

Réponses:

C'est un résultat classique de Winograd: sur la multiplication de matrices 2x2 .

Strassen a montré que l'exposant de la multiplication matricielle est le même que l'exposant du rang tensoriel des tenseurs multiplicateurs matriciels: la complexité algébrique de multiplication matricielle est ssi le rang tensoriel de (le tenseur de multiplication matricielle correspondant à la multiplication de deux matrices ) est . L'algorithme de Strassen utilise la direction facile pour déduire un de la limite supérieure . $n\times n$ $O(n^\alpha)$ $\langle n,n,n \rangle$ $n\times n$ $O(n^\alpha)$ $O(n^{\log_27})$ $R(\langle 2,2,2 \rangle) \leq 7$

Le résultat de Winograd implique que . Landsberg a montré que le rang frontalier de est également de 7, et Bläser et al. a récemment étendu ce soutien au grade et au grade de soutien à la frontière. Le rang de frontière et le rang de support sont des notions de rang plus faibles (= plus petites) qui ont été utilisées (dans le cas du rang de frontière) ou proposées (dans le cas du rang de support) dans les algorithmes de multiplication matricielle rapide. $R(\langle 2,2,2 \rangle)=7$ $\langle 2,2,2 \rangle$

Yuval Filmus
la source

Vous pouvez trouver le résultat sur:

S.Winograd, Sur la multiplication de matrices 2 × 2 , Algèbre linéaire et Appl. 4 (1971), 381–388, MR0297115 (45: 6173).

Stella Biderman
la source