Complexité de la multiplication de matrices

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.

Concepts associés (3)

Cours associés (15)

Séances de cours associées (215)

MOOCs associés (9)

Matrix multiplication algorithm

Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in many fields including scientific computing and pattern recognition and in seemingly unrelated problems such as counting the paths through a graph. Many different algorithms have been designed for multiplying matrices on different types of hardware, including parallel and distributed systems, where the computational work is spread over multiple processors (perhaps over a network).

Complexité de la multiplication de matrices

Computational complexity of mathematical operations

The following tables list the computational complexity of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine. See big O notation for an explanation of the notation used. Note: Due to the variety of multiplication algorithms, below stands in for the complexity of the chosen multiplication algorithm. This table lists the complexity of mathematical operations on integers.

CS-233: Introduction to machine learning

Machine learning and data analysis are becoming increasingly central in many sciences and applications. In this course, fundamental principles and methods of machine learning will be introduced, analy

CS-433: Machine learning

Machine learning methods are becoming increasingly central in many sciences and applications. In this course, fundamental principles and methods of machine learning will be introduced, analyzed and pr

MGT-499: Statistics and data science

This class provides a hands-on introduction to statistics and data science, with a focus on causal inference, applications to sustainability issues using Python, and dissemination of scientific result

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algèbre Linéaire (Partie 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Programmation dynamique : sous-séquence commune la plus longue CS-250: Algorithms I

Explore la programmation dynamique en mettant l'accent sur le problème de la sous-séquence commune la plus longue et ses solutions efficaces.

Composite d'applications MATH-113: Algebraic structures

Couvre le concept de composite d'applications et l'importance de certaines hypothèses dans la multiplication matricielle.

Les arbres de récurrence et la multiplication matricielle CS-250: Algorithms I

Couvre les arbres de récursion, le problème de sous-réseau maximal et les approches de multiplication matricielle.