Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Algorithme de Strassen
Résumé
vignette|Algorithme de Strassen où sont représentés les matrices Ci,j ainsi que les 7 nouvelles matrices Mi
En mathématiques, plus précisément en algèbre linéaire, l’algorithme de Strassen est un algorithme calculant le produit de deux matrices carrées de taille n, proposé par Volker Strassen en 1969. La complexité de l'algorithme est en , avec pour la première fois un exposant inférieur à celui de la multiplication naïve qui est en . Par contre, il a l'inconvénient de ne pas être stable numériquement.
L'algorithme de Strassen est le premier algorithme de multiplication de matrices demandant asymptotiquement un nombre d'opérations arithmétiques (additions et multiplications) inférieur à . Ce n'est cependant pas le premier algorithme « plus rapide » que l'algorithme naïf : Shmuel Winograd avait donné en 1967 un algorithme demandant environ multiplications dans le cas de matrices à coefficients dans un anneau commutatif, contre environ pour l'algorithme naïf ; mais on ignorait s'il était possible de multiplier des matrices en complexité sous-cubique.
De surcroît, l'article de Strassen montre comment utiliser l'algorithme rapide de multiplication pour calculer l'inverse d'une matrice avec la même borne de complexité. Il prouve ainsi que l'algorithme usuel du pivot de Gauss n'est pas optimal.
Le travail de Strassen a ouvert un champ de recherche important en informatique théorique. La question centrale dans ce domaine est de savoir s'il est possible de multiplier deux matrices en opérations pour arbitrairement proche de . Parmi les résultats importants qui suivront, on peut citer notamment l'algorithme de Coppersmith-Winograd (1987), dont la complexité est longtemps restée la meilleure connue.
Complexité de la multiplication de matrices
Soit R un anneau unitaire et soient A et B des matrices carrées de taille n dont les coefficients sont éléments de l'ensemble sous-jacent à R. Pour des raisons de simplicité, on traite le cas où n est une puissance de 2. On peut toujours se ramener à ce cas en rajoutant éventuellement des colonnes et des lignes de zéros.
Source officielle
À 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.