6.4.2 : Multiplication de matrices rapide
Nous allons nous limiter aux matrices carrées de taille
Le concept de base est de remplacer le plus possible les mutiplications par les additions car les additions ont une complexité en
Les méthodes de multiplication de matrices rapide ne sont efficaces que sur de très grandes matrices,
, même si techniquement une addition est plus rapide qu'une mutiplication sur un processeur,
cycles contre
.
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
à
, sont eux mêmes des matrices de taille supérieure à
, la plus faible complexité de l'algorithme va se faire sentir.