Discussion :

[kiroukou]

Bonjour à tous,

Voila je cherche un moyen d'optimiser les multiplications de mes matrices 4x4.
J'ai lu sur le net que S. Winograd et D. Coppersmith avaient trouvés un moyen mais je n'ai pas trouvé de bonne doc dessus.

Je m'en remet à vous si vous connaissez leurs technique, ou si vous avez là votre

Merci
++

[Laurent Gomila]

Si c'est du C++ tu as des optimisations interessantes à base de templates. Sinon algorithmiquement parlant, aucune idée.

[JHelp]

Une chose, sous quelle forme stockes-tu tes matrices tableau à une ou deux dimensions ?
Tes matrices ont elles une forme particuliéres ? Par exemple se sont des transformations dans un espace 3D (comme rotation, translation, scale)
Si ce sont des matrices quelconques, je ne vois pas comment on peut optimiser au niveau calcul (c'est à dire comment éviter 16 fois 4 multiplications et 3 additions. Tu peux gagner sur la structure en les stockant dans un tableau à une dimension, pour simplifier les acces et gagner donc tu temps.
Si tu trouves un meilleur moyen qui évite les 16 fois 4 multiplications et 3 additions pour les matrices quelconque, merci de le poster ici.

[nicolas581]

Oui on peut faire mieux, l'algorithme de strassen est inférieure à O(n^3) mais j'ai la flemme de voir si pour des matrices petites il y a un gain
Une bonne explication :
http://gersoo.free.fr/docs/stras/stras.html
Il y a même mieux que Strassen d'après cette page.

[Charlemagne]

Le produit de 2 matrices est d'ordre N^3.
Je sais qu'il existe des algorithmes qui permettent de réduire l'ordre (du genre O(N^2.5), principalement pour des longueurs en puissance de 2 (N=2^P).
Ces méthodes sont assez compliqués, et ne se justifient pas pour une matrice 4x4.


Par contre, il y a la possibilité d'utiliser des instructions SIMD du processeur.
L'inconvenient, c'est que c'est dépendant du processeur.

Chez Intel, il y a MMX, SSE (à partir du P3), SSE2 (à partir du P4).
Ca permet de calculer en parallele.

Par exemple si tu calcules avec des floats, SSE permet de regrouper 4 floats dans un registre.
Cela permet de caculer le produit d'une matrice 4x4 par un vecteur en 4 multiplications et 4 additions (au lieu de 16 et 16)

Imbattable...

[JHelp]

En fait je viens de trouver l'algo dont tu parlais.
C'est génial.
En fait si tu combines le lien :
http://www.e-paranoids.com/s/st/strassen_algorithm.html
avec le lien :
http://mathworld.wolfram.com/StrassenFormulas.html
tu peux trouver ce qui t'interesse.
En effet dans le prmier lien il disent que si la matrice fait pas 2 puissance n x 2 puissance n, il faut l'agrandir pour que ca le fasse. Donc pour 4x4, rien à faire.
ensuite ta matrice 4 x 4, toujours d'aprés le premier lien il faut la découper en sous matrices, puis de la on peut utilise le second lien.
Admetons que tes matrices soit

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
  (a11 a12 a13 a14)
  (a21 a22 a23 a24)
A=(a31 a32 a33 a34)
  (a41 a42 a43 a44)
 
  (b11 b12 b13 b14)
  (b21 b22 b23 b24)
B=(b31 b32 b33 b34)
  (b41 b42 b43 b44)

alors si on note :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    (aij ai(j+1))
Aij=(a(i+1)j a(i+1)(j+1))
 
    (bij bi(j+1))
Bij=(b(i+1)j b(i+1)(j+1))

alors elles deviennent :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
  (A11 A12)
A=(A21 A22)
 
  (B11 B12)
B=(B21 B22)

De la suffit dappluquer l'algo fournit dans le second lien.
On se retrouve alors avec des multiplications de matrices 2x2 auquelles s'aplliquent également l'algo du second lien.
JHelp

[kiroukou]

Salut à tous et merci pour vos réponses
En fait ce n'est pas en C++, c'est pour de l'actionscript (que pas mal d'entre vous ne doivent pas connaitre C'est le language de Flash )
Ma matrice est stockée dans nu tableau à une seule dimension. Avant je ne faisais pas comme ceci, et là j'obtiens deja un bon gain de performance rien qu'en faisant ceci.

Je n'ai pas acces a l'assembleur du processeur, je ne peux donc pas jouer là dessus

Merci JHelp c'est exactement ce que je cherchais. Je n'avais pas compris qu'il fallait decouper ma matrice en matrices 2x2. Je vais tenter cet algo pour voir si cela me fais gagner qq ms. Je sais que pour des gens venant du C ou C++ cela n'est pas intéréssant mais pour Flash la moindre optimisation à toute sont importances

Je vous remercie encore enormement , et je posterai mon code si j'arrive à qq chose

++

[kiroukou]

Salut,
J'ai un petit doute quand à cette écriture :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    (A11 A12)
A=(A21 A22)
 
    (B11 B12)
B=(B21 B22)

Il semblerai que les elements a14 .. a44 ne soient jamais calculés.

Est ce moi qu ime trompe où bien il y a une petite erreur d'écriture?

++

[PINGOUIN_GEANT]

A mon avis tu ne devrais pas utiliiser Strassen et faire la multiplication de matrices toute simple pour un ordre égal à 4, car cet algorithme n'est bien que pour des ordres élevés.
D'ailleurs :

which is less than M(n) for n > 654.

[kiroukou]

Oui je crosi que tu as raison PINGUOUIN_GEANT.
Dommage J'aurai bien pensé qu'il existe des optimisations...

Merci encore
++

[SuperCed]

Il existe des librairies qui font ça très bien et surtout, qui utilisent les instructions vectorielles des processeurs récents : SSE 2 sur Intel, 3DNow sur AMD, ou encore l'Altivec de Motorola. Ceci permet de gagner 3 ou 4 fois plus de temps sur ce type de calcul.