Matrixmultiplikation in

13

Ich suchte nach Matrixmultiplikationsalgorithmen. Also habe ich zum ersten Mal Wiki- Matrixmultiplikationsalgorithmen besucht. In Referenzen habe ich einen Artikel gefunden, in dem behauptet wird, dass der Algorithmus verwendetÖ(n2lÖG(n)) wird. Ich würde den Artikel lesen, aber er ist kompliziert und Das Lesen dauert zu lange, aber wenn jemand diesen Artikel liest oder etwas über diesen Algorithmus weiß, stimmt das? und wissen Sie etwas über die Grundidee davon, um es ein wenig zu beschreiben?

Vielen Dank im Voraus, ich weiß, dass es eine allgemeine Frage ist, aber wenn ich einen guten Ansatz gefunden habe, werde ich Details erfahren.

ds.algorithms linear-algebra matrix-product Saeed
quelle
5
Ich halte es für nützlich, die eigene Frage besser zu verstehen. Suchen Sie einen sequentiellen oder einen parallelen Algorithmus? Es sind keine sequentiellen Algorithmen für die Matrixmultiplikation mit der Zeit O (n ^ 2 log n) bekannt, und das Paper von Eve ist ein Teilergebnis für solche Algorithmen (ich habe das Paper nicht gelesen, ich habe es nur überflogen). Wenn Sie sich für die parallele Zeit interessieren, dann ist die parallele Zeit O (log n) (unter der Annahme einer Skalaraddition und einer Skalarmultiplikation in konstanter Zeit) Standard und eine Erklärung finden Sie zB in dem Buch Computational Complexity von Papadimitriou.
Tsuyoshi Ito
2
(1) Bearbeiten Sie Ihre Frage so, dass klar ist, dass Sie nach sequentiellen Algorithmen fragen. (2) Mir ist aufgefallen, dass Sie das Tag [Quantum-Computing] hinzugefügt haben. Bitte bearbeiten Sie Ihre Frage, um den Zusammenhang mit Quantencomputern zu erläutern. (Meine Vermutung ist, dass Ihre Frage durch Quantencomputer motiviert ist, aber Ihre eigene Erklärung ist weitaus nützlicher als jede Vermutung.)
Tsuyoshi Ito
2
Ich würde empfehlen, diese Frage zuerst zu löschen und später erneut zu posten, wenn Sie feststellen, dass Sie eine Frage haben.
Suresh Venkat
3
@Saeed: Dieses Problem wurde auf der Meta-Website diskutiert. Derzeit handelt es sich um die Richtlinie der Website. Wenn Sie die Richtlinie diskutieren möchten, verwenden Sie die Meta-Richtlinie. Auf der anderen Seite können Sie die Frage modifizieren und vermeiden, das Papier zu erwähnen, um es zum Thema zu machen, z. B. die Frage zu modifizieren, um "Was ist der bekannteste Algorithmus für die Matrixmultiplikation in Modell X" zu werden. und das wäre themenbezogen. (Randnotiz: Wenn Sie die Korrektheit eines unveröffentlichten Papiers nicht selbst überprüfen können und es zitieren möchten, sollten Sie warten, bis es von Fachleuten begutachtet und veröffentlicht wird.)
Kaveh
3
Verwandte Diskussion zu Meta: Ist es in Ordnung, nach der Richtigkeit von Preprints zu kurbelfreundlichen Themen zu fragen? Ich behaupte nicht, dass alles, was auf dieser Seite steht, auf diese Frage zutrifft, aber es ist zumindest eng miteinander verbunden.
Tsuyoshi Ito

Antworten:

34

Ich bin vor ungefähr einem Jahr auf diese Zeitung gestoßen, bin aber nicht dazu gekommen, sie genau zu lesen. Ich kann Ihnen sagen, dass der Ansatz nicht für richtig gehalten wird. Auf Seite 36 desselben Papiers ist ein Kommentar von Don Knuth beigefügt, der darauf hinweist, was als schwerwiegender Mangel des Ansatzes anzusehen ist.

Um dieses Papier zu verstehen, müssen Sie sich mit Gruppenalgebra und Repräsentationstheorie vertraut machen. Es wird schwierig, wenn Sie so etwas noch nicht gesehen haben.

Ryan Williams
quelle