6.4.2 : Multiplication de matrices rapide
Nous allons nous limiter aux matrices carrées de taille $N\times N$ pour cette partie, ce qui sera suffisant pour illustrer notre propos.Le concept de base est de remplacer le plus possible les mutiplications par les additions car les additions ont une complexité en $O\left(N^2\right)$ alors que les multiplications ont une complexité en $O\left(N^3\right)$ . Cela est intéressant uniquement dans de cadre d'une multiplication de matrice par blocs.
Les méthodes de multiplication de matrices rapide ne sont efficaces que sur de très grandes matrices, $N > 100$
, même si techniquement une addition est plus rapide qu'une mutiplication sur un processeur, $4$
cycles contre $6$
.
Si les matrices utilisées sont trop petites, les performances de calculs seront identiques ou dégradées par rapport à l'algorithme classiqe.
Mais si les éléments des matrices, de $a$
à $h$
, sont eux mêmes des matrices de taille supérieure à $50$
, la plus faible complexité de l'algorithme va se faire sentir.