Worldlex Wiki La multiplication matricielle étant une opération fondamentale dans de nombreux algorithmes numériques , d'importants travaux ont été consacrés à l' optimisation de ces algorithmes . On trouve des applications de la multiplication matricielle dans de nombreux domaines du calcul, notamment le calcul scientifique et la reconnaissance de formes , ainsi que dans des problèmes apparemment sans lien, comme le dénombrement des chemins dans un graphe . De nombreux algorithmes ont été conçus pour multiplier des matrices sur différents types de matériel, y compris les systèmes parallèles et distribués , où la charge de calcul est répartie sur plusieurs processeurs (éventuellement sur un réseau).
L'application directe de la définition mathématique de la multiplication matricielle donne un algorithme dont complexité temporelle est sur le corps pour multiplier deux matrices notation grand O ). Des bornes asymptotiques plus précises sur le temps nécessaire à la multiplication de matrices sont connues depuis l' algorithme de Strassen dans les années 1960, mais la complexité optimale (c'est-à-dire la complexité algorithmique de la multiplication matricielle ) reste inconnue. complexité asymptotique d'un algorithme de multiplication matricielle est Williams , Xu, Xu et Zhou. Cependant, cet algorithme est un algorithme galactique en raison des grandes constantes et ne peut pas être réalisé en pratique.
définition de la multiplication matricielle est la suivante : siComportement du cache
Le taux d'échecs de cache de la multiplication matricielle récursive est identique à celui d'une version itérative par blocs , mais contrairement à cette dernière, l'algorithme récursif est insensible au cache : aucun paramètre de réglage n'est nécessaire pour obtenir des performances optimales, et il se comporte bien dans un environnement multiprogrammé où la taille du cache est dynamique en raison de l'utilisation de l'espace cache par d'autres processus. (L'algorithme itératif simple est également insensible au cache, mais beaucoup plus lent en pratique si la disposition de la matrice n'est pas adaptée à l'algorithme.)
Le nombre de défauts de cache occasionnés par cet algorithme, sur une machine dotée de
Algorithmes sous-cubiques
Il existe des algorithmes plus performants que les algorithmes directs. Le premier à avoir été découvert est l'algorithme de Strassen , conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide ». Il repose sur une méthode de multiplication de deux matrices 2×2 qui ne nécessite que 7 multiplications (au lieu des 8 habituelles), moyennant quelques additions et soustractions supplémentaires . Son application récursive donne un algorithme dont le coût multiplicatif est O( n² ). L'algorithme de Strassen est plus complexe et sa stabilité numérique est moindre que celle de l'algorithme naïf , mais il est plus rapide lorsque 100"}},"i":0}}] n 100"}},"i":0}}] > 100 environ et est présent dans plusieurs bibliothèques, comme BLAS . Il est particulièrement utile pour les grandes matrices sur des domaines exacts tels que les corps finis , où la stabilité numérique n'est pas un problème.
L'algorithme de Strassen étant effectivement utilisé dans des logiciels de calcul numérique et des systèmes de calcul formel , l'amélioration des constantes sous-jacentes à la notation grand O présente un intérêt certain. Le tableau ci-après compare les principaux aspects de la version améliorée, basée sur la multiplication récursive de matrices par blocs 2×2 via 7 multiplications de matrices par blocs. Comme d'habitude, indique les dimensions de la matrice et la taille mémoire requise.
| Année | Référence | #multiplications matricielles par étape | #additions de matrice par étape | opérations arithmétiques totales | Complexité totale des E/S |
|---|---|---|---|---|---|
| 1969 | Strassen | 7 | 18 | ||
| 1971 | Winograd | 7 | 15 | ||
| 2017 | Karstadt, Schwartz | 7 | 12 | ||
| 2023 | Schwartz, Vaknin | 7 | 12 |
Il est connu qu'un algorithme de type Strassen avec une étape de matrice par blocs 2×2 nécessite au moins 7 multiplications de matrices par blocs. En 1976, Probert a montré qu'un tel algorithme requiert au moins 15 additions (soustractions comprises) ; toutefois, cette démonstration reposait sur l'hypothèse implicite que les blocs et la matrice par blocs 2×2 étaient représentés dans la même base. Karstadt et Schwartz ont effectué des calculs dans des bases différentes et ont compensé 3 additions par des transformations de base moins coûteuses. Ils ont également prouvé qu'il est impossible de descendre en dessous de 12 additions par étape en utilisant des bases différentes. Dans des travaux ultérieurs, Beniamini et al. ont appliqué cette technique de changement de base à des décompositions plus générales que les matrices par blocs 2×2 et ont amélioré la constante dominante de leurs temps d'exécution.
L'amélioration de l'algorithme de Strassen en termes de complexité asymptotique reste une question ouverte en informatique théorique . L' exposant de multiplication matricielle , généralement noté , est le plus petit nombre réel pour lequel deux matrices quelconques sur un corps peuvent être multipliées entre elles par des opérations sur le corps. La meilleure borne actuelle pour est , obtenue par Alman, Duan, Williams , Xu, Xu et Zhou . Cet algorithme, comme tous les algorithmes récents de ce domaine de recherche, est une généralisation de l'algorithme de Coppersmith-Winograd, proposé par Don Coppersmith et Shmuel Winograd en 1990 notation grand O est si élevé que ces algorithmes ne sont intéressants que pour des matrices trop grandes pour être traitées par les ordinateurs actuels. Victor Pan a proposé des algorithmes de multiplication de matrices sous-cubiques réalisables avec un exposant légèrement supérieur à 2,77, mais en contrepartie avec un coefficient constant caché beaucoup plus petit.
L'algorithme de Freivalds est un algorithme de Monte Carlo simple qui, étant donné les matrices A DeepMind a introduit AlphaTensor, un réseau neuronal qui, à l'aide d'une analogie avec un jeu solo, a inventé des milliers d'algorithmes de multiplication matricielle, dont certains déjà découverts par l'homme et d'autres inédits. Les opérations étaient limitées au au corps fini
Algorithmes parallèles et distribués
Parallélisme de mémoire partagée
L' algorithme de type diviser pour régner décrit précédemment peut être parallélisé de deux manières pour les multiprocesseurs à mémoire partagée . Ces méthodes reposent sur le fait que les huit multiplications matricielles récursives dans
Les opérations peuvent être effectuées indépendamment les unes des autres, de même que les quatre sommations (bien que l'algorithme doive « joindre » les multiplications avant d'effectuer les sommations). En exploitant le parallélisme complet du problème, on obtient un algorithme qui peut être exprimé sous forme de pseudocode de type fork-join :
chemin critique de accélération maximale possible est deAlgorithmes pour les maillages
Il existe divers algorithmes de multiplication sur des maillages . Pour la multiplication de deux matrices n × n sur un maillage bidimensionnel standard, l' algorithme de Cannon 2D permet d'effectuer la multiplication en 3n - 2 étapes, ce nombre étant réduit de moitié pour des calculs répétés. L'utilisation d'un tableau standard est inefficace car les données des deux matrices n'arrivent pas simultanément et doivent être complétées par des zéros.
Le résultat est encore plus rapide sur un maillage croisé à deux couches, où seulement 2n - 1 étapes sont nécessaires. Les performances s'améliorent encore pour les calculs répétés, atteignant une efficacité de 100 %. Le réseau maillé croisé peut être considéré comme un cas particulier de structure de traitement non planaire (c'est-à-dire multicouche).
Dans un maillage 3D avec n 3 éléments de traitement, deux matrices peuvent être multipliées en utilisant l'algorithme DNS.