Quel est le meilleur algorithme de multiplication de matrice?
Quel est le meilleur algorithme de multiplication de matrice? Ce qui signifie " le meilleur'pour moi? Il désigne la manière la plus rapide et prêt pour les machines d'aujourd'hui.
Veuillez donner des liens vers de pseudo si vous le pouvez.
- Comment voulez-vous multiplier une matrice par la main?
- Voulez-vous un pour les matrices générales, ou avez-vous utile de contraintes sur les matrices, comme triangulaire supérieure ou diagonale?
- Est-ce pour les un programme, ou autre chose comme le travail scolaire? La multiplication de matrice est assez simple: 1) vérifier que les dimensions sont d'accord (par exemple 3x3 * 3x1 et pas 3x3 * 1x3), 2) multiplier les champs correspondants ensemble et ajouter pour arriver à la finale champ. en.wikipedia.org/wiki/Matrix_multiplication
- Quelle est la taille des matrices? Fixe? Les petits? Big? Incroyablement grand?
- Le vote pour la fermer comme trop large.
Vous devez vous connecter pour publier un commentaire.
BLAS est le meilleur prêt-à-utilisation efficace de multiplication de matrice de la bibliothèque. Il ya beaucoup de différents mise en œuvre. Voici un test que j'ai fait pour certaines implémentations sur un MacBook Pro équipé d'un dual core Intel Core 2 Duo 2,66 GHz :
Il y a aussi d'autres implémentations commerciales que je n'ai pas fait de test ici :
Le meilleur algorithme de multiplication de matrice est celle que quelqu'un avec architecturale détaillée de connaissances a déjà réglé la main pour votre plate-forme cible.
Il y a beaucoup de bonnes bibliothèques qui fournissent à l'écoute de la matrice-multiplier les implémentations. Utiliser l'un d'eux.
Il y a sans doute mieux, mais ce sont ceux que j'ai la tête de (mieux que le cube standard de la complexité de l'algorithme).
Strassen du - O(N^2.8)
Chaudronnerie Winograd - O(N^2.376)
Pourquoi le pseudo-code? Pourquoi mettre en place vous-même? Si la vitesse est votre problème, il existe des algorithmes très performants disponibles qui incluent des optimisations pour certains jeux d'instructions (par exemple SIMD), la mise en œuvre de celles-ci par vous-même n'offre aucun avantage réel (à part peut-être l'apprentissage),
Jeter un oeil à différentes BLAS implémentations, comme:
http://www.netlib.org/blas/
http://math-atlas.sourceforge.net/
Voici les algorithmes de cours du MIT et de la multiplication de matrice de la conférence
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-19-shortest-paths-iii-all-pairs-shortest-paths-matrix-multiplication-floyd-warshall-johnson/
de multiplication de matrice - O(n^3)
L'algorithme de Strassen - O(n^2.8) http://en.wikipedia.org/wiki/Strassen_algorithm
Chaudronnerie–Winograd - O(n^2.376) http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm
Dépend de la taille de la matrice, et si elle est peu ou pas.
Pour les petites et moyennes matrices denses, je crois qu'une certaine variation sur le "naïf" O(N^3) l'algorithme est une victoire, si vous faites attention à cache-cohérence et de l'utilisation de la plate-forme du vecteur instructions.
Organisation des données est important, pour les cas où votre norme de la matrice de mise en page est en cache-hostiles (par exemple, la colonne principale * row-major), vous devriez essayer binaire de décomposition de la matrice de multiplication -- même si vous n'utilisez pas de Strassen ou par d'autres "rapide" algorithmes, cet ordre des opérations peut donner un "cache-inconscients" algorithme qui réalise automatiquement un bon usage de chaque niveau de cache. Si vous avez le luxe de réorganiser vos matrices, vous pouvez essayer de combiner cela avec un bit interleaved (ou "ordre") de commande des éléments de données.
Enfin, n'oubliez pas: l'optimisation prématurée est la racine de tous les maux. Et quand il n'est pas prématuré de plus, toujours profil & test avant, pendant, et après l'optimisation....
Il existe un algorithme d'appel de la
Cannon's algorithm
distribué algorithme de multiplication de matrice. Plus iciIl n'y a pas de "meilleur" algorithme pour toutes les matrices sur tous les Processeurs modernes.
Vous aurez besoin de faire quelques recherches dans les nombreuses méthodes disponibles, et ensuite trouver un meilleur ajustement de la solution à des problèmes particuliers qui vous sont calcul sur le matériel que vous travaillez avec.
Par exemple, le "plus rapide" chemin sur votre plate-forme matérielle peut être d'utiliser un "ralentissement" de l'algorithme, mais demandez à votre GPU pour l'appliquer à 256 matrices en parallèle. Ou à l'aide d'un "rapide" à des fins générales (mxn) algorithme peut produire des résultats beaucoup plus lents que d'utiliser de manière optimale la matrice de 3x3 se multiplier. Si vous voulez vraiment être rapide, alors vous pouvez envisager d'entrer dans la bare metal pour vous assurer de faire la meilleure utilisation de certaines fonctionnalités du PROCESSEUR comme instructions SIMD, direction de la prévision et de la cohérence de cache, au détriment de la portabilité.