Multiplication matricielle en

13

Je cherchais sur la multiplication matricielle, donc j'ai d'abord visité les algorithmes de multiplication matricielle wiki , dans les références, j'ai trouvé un article qui prétend utiliser l' algorithme O(n2log(n)) , je vais lire l'article mais c'est compliqué et Will prend trop de temps pour le lire, mais s'il y a quelqu'un qui lit cet article ou qui connaît cet algorithme, est-ce vrai? et connaissez-vous l'idée de base de cela pour la décrire un peu.

Merci d'avance, je sais que c'est une question un peu générale mais, si je trouve que c'est une bonne approche, je vais apprendre les détails.

ds.algorithms linear-algebra matrix-product Saeed
la source
5
Je pense qu'il est utile de mieux comprendre votre propre question. Vous recherchez un algorithme séquentiel ou un algorithme parallèle? Aucun algorithme séquentiel pour la multiplication matricielle avec le temps O (n ^ 2 log n) n'est connu, et l'article d'Eve est un résultat partiel vers de tels algorithmes (je n'ai pas lu l'article, je l'ai simplement survolé). Si vous vous souciez du temps parallèle, alors le temps parallèle O (log n) (en supposant l'addition scalaire et la multiplication scalaire en temps constant) est standard et vous pouvez trouver des explications dans, par exemple, le livre Computational Complexity de Papadimitriou.
Tsuyoshi Ito
2
(1) Veuillez modifier votre question afin qu'il soit clair que vous posez des questions sur les algorithmes séquentiels. (2) J'ai réalisé que vous aviez ajouté le tag [calcul quantique]. Veuillez modifier votre question pour expliquer la relation avec l'informatique quantique. (Je suppose que votre question est motivée par l'informatique quantique, mais votre propre explication est beaucoup plus utile que toute supposition.)
Tsuyoshi Ito
2
Je vous recommande de supprimer cette question d'abord, puis de republier plus tard si vous trouvez que vous avez une question.
Suresh Venkat
3
@Saeed: Ce problème a été discuté sur la méta et actuellement c'est la politique du site, si vous voulez discuter de la politique, utilisez la méta. D'un autre côté, vous pouvez modifier la question et éviter de mentionner le papier pour le rendre sur le sujet, par exemple en modifiant la question pour devenir "quel est l'algorithme le plus connu pour la multiplication matricielle dans le modèle X?" et ce serait sur le sujet. (note latérale: si vous ne pouvez pas vérifier vous-même l'exactitude d'un article non publié et que vous voulez le citer, vous devez attendre qu'il soit révisé par des pairs et publié.)
Kaveh
3
Discussion connexe sur Meta: est-il correct de poser des questions sur l'exactitude des préimpressions sur des sujets conviviaux? Je ne prétends pas que tout ce qui est écrit sur cette page s'appliquera à cette question, mais elle est au moins étroitement liée.
Tsuyoshi Ito

Réponses:

34

J'ai rencontré ce document il y a environ un an, mais je n'ai pas réussi à le lire attentivement. Je peux vous dire que l'approche n'est pas considérée comme correcte. À la page 36 du même document, il y a un commentaire ci-joint de Don Knuth, qui souligne ce qui semble être une grave lacune de l'approche.

Pour comprendre cet article, vous devrez vous renseigner sur l'algèbre de groupe et la théorie de la représentation. Ce sera difficile si vous n'avez jamais vu ce genre de matériel auparavant.

Ryan Williams
la source