Concept

Complexité de la multiplication de matrices

Résumé
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 opérations sur le corps de base pour multiplier deux matrices d'ordre . 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 est encore inconnu en 2023. Il s'agit là d'une question ouverte majeure en informatique théorique. Toutefois, ce nombre est au moins d'ordre . En octobre 2022, la meilleure complexité en temps de multiplication de matrices est , valeur annoncée par Ran Duan, Hongxun Wu et Renfei Zhou dans une prépublication. Cett borne améliore la borne de donnée par Josh Alman et . Cependant, cette amélioration et d'autres améliorations similaires de l'algorithme de Strassen ne sont pas utilisées en pratique, car elles sont des « algorithmes galactiques » en ce sens que la constante du est si élevée qu'ils ne sont utiles que pour les matrices trop grandes pour être traitées par les ordinateurs actuels. Produit matriciel Si et sont deux matrices d'ordre sur un anneau, leur produit est aussi une matrice d'ordre sur cet anneau, dont les entrées sont : L'approche la plus simple pour calculer le produit de deux matrices et d'ordre consiste à évaluer les expressions arithmétiques issues de la définition de la multiplication matricielle. Cet algorithme nécessite, dans le pire des cas multiplications et additions scalaires pour calculer le produit de deux matrices carrées d'ordre .
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.