Complexité de la multiplication de matrices

Carte Commune · n° 335548

En informatique théorique, la complexité de la multiplication de matrices est le nombre d'opérations requises pour l'opération de produit matriciel. Les algorithmes de multiplication de matrices constituent un sujet central dans les algorithmes théoriques et numériques en algèbre linéaire numérique et en optimisation, donc déterminer la complexité en temps du produit est d'une importance pratique. L'application directe de la définition mathématique de la multiplication de matrices donne un algorithme qui nécessite Θ(n3) opérations sur le corps de base pour multiplier deux matrices d'ordre n. Il existe des algorithmes qui demandent moins d'opérations que le simple « algorithme naïf ». Le premier de ces algorithmes est l'algorithme de Strassen, conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide ». Le nombre minimal d'opérations du corps de base nécessaires pour multiplier deux matrices carrées d'ordre n est encore inconnu en 2023. Il s'agit là d'une question...

Lire sur Wikipédia