Algorithme de Strassen pour la multiplication de matrices

Méthode

Soient 𝐴, 𝐵 deux matrices carrées d'ordre 𝑛 et 𝐶 leur produit. La façon usuelle de calculer 𝐶,

C = AB = ( c ij ) ; 1 i , j n avec c ij = a ik b kj { C = AB = (c_{ij}); 1 leslant i, j leslant n avec c_{ij} = sum a_{ik}b_{kj} }

Algorithme naïf

L'algorithme classique est le suivant :

1
MULTIPLIER-MATRICES(A, B)
2
Soit n la taille des matrices carrés A et B
3
Soit C une matrice carré de taille n
4
Pour i 1 à n faire
5
 Pour j 1 à n faire
6
 ci ; j  0
7
 Pour k1 à n faire
8
 ci; j  ci; j + ai; k * bk; j
9
 Fin pour
10
 Fin pour
11
Fin pour
12
Renvoyer C