Beweise, dass die Matrixmultiplikation in quadratischer Zeit durchgeführt werden kann?

59

Es wird allgemein vermutet, dass , der optimale Exponent für die Matrixmultiplikation, tatsächlich gleich 2 ist. Meine Frage ist einfach: $\omega$

Welche Gründe haben wir für die Annahme, dass ? $\omega = 2$

Ich kenne schnelle Algorithmen wie Coppersmith-Winograd, aber ich weiß nicht, warum diese als Beweis für könnten . $\omega = 2$

Naiv scheint es mir ein klassisches Beispiel zu sein, bei dem eine Community nur hofft, dass ein Ergebnis aus rein ästhetischen Gründen wahr ist. Ich würde gerne wissen, ob das hier im Wesentlichen der Fall ist.

ds.algorithms linear-algebra matrix-product Steve Flammia
quelle

12

ω = 2

$\omega=2$

5

ω > 2

$\omega > 2$

2

@ Ryan, hoffen wir, dass Strassen cstheory.stackexchange liest. :)

Steve Flammia

3

Ω (n \log n)

$\Omega(n\log n)$

ω = 2

$\omega = 2$

2

$2$

5

ω

$\omega$

ω

$\omega$

20

Ich möchte den Kommentar von Mark Reitblatt und die Antwort von Amir Shpilka ergänzen. Erstens ist eine der von Cohn, Kleinberg, Szegedy und Umans vorgebrachten Vermutungen nicht gruppentheoretisch, sondern rein kombinatorisch (Konj. 3.4 in ihrem FOCS'05-Aufsatz ). Diese Vermutung besagt, dass die "starke USP-Kapazität beträgt $\frac{3}{2^{2/3}}$ $\frac{3}{2^{2/3}}$

(Für ihre andere gruppentheoretische Vermutung 4.7 kenne ich keinen ähnlichen Beweis für Plausibilität, der über die Intuition hinausgeht.)

Zweitens stimme ich Amir Shpilka zu, dass die Kette vergangener Algorithmen etwas ad-hoc wirkt. Das Schöne am gruppentheoretischen Ansatz ist jedoch, dass fast alle (nicht alle) der vorherigen Algorithmen in diesem Ansatz formuliert werden können. Obwohl die verschiedenen gruppentheoretischen Konstruktionen in [CKSU] äußerlich ein wenig ad-hoc erscheinen mögen, erscheinen sie im Kontext des gruppentheoretischen Rahmens wesentlich natürlicher und weniger ad-hoc (zumindest für mich) als viele andere die vorherigen Algorithmen.

Joshua Grochow
quelle

Wenn ich an Kapazität denke, denke ich an unabhängige Sets und Cliquen. Was ist das Wörterbuch zwischen USPs und der expliziten Konstruktion des zugrunde liegenden Diagramms und gibt es eine Struktur für diese Diagramme?

T ....

28

$\omega=2$ $\omega=2$

Amir Shpilka
quelle

20

$\omega = 2$

$A$ $B$ $n$ $n$ $C = AB$ $C(i,j) = \sum_{k=1}^n A(i,k) B(k,j)$ $A$ $B$ $n$ $C = A*B$ $C(i) = \sum_{k=1}^n A(k)B(i-k)$ $\tilde{O}(n)$ $O(n^2)$ $\tilde{O}(n^2)$ Zeitalgorithmus für die Matrixmultiplikation. Die Frage ist: Was ist das Analogon der Fouriertransformation, das bei der Matrixmultiplikation helfen kann?

Arnab
quelle

-1

$O(n^{2} log(n^2))$ $\omega = 2$

Chad Brewbaker
quelle

1

ω

$\omega$

c

$c$

O (n^{c})

$O(n^c)$

O (n^{2} \log^{10} n)

$O(n^2 \log^{10} n)$

2

$2$

Ω (n^{2} \log n)

$\Omega(n^2\log n)$

@SashoNikolov Danke für den Hinweis. Hat jemand versucht, ein neuronales Netz für das Boolesche Matmul A * B = C zu trainieren? [A-Einträge, B-Einträge, C-Einträge] -> Bool (richtig oder falsch multiplizieren). Neugierig, welche Schaltkreise die Steigung anständig / Aussetzer einfallen lassen; Wenn trainierte Rennstrecken Attraktoren in der Nähe von Primärzerlegungen haben. Bei 3x3, 4x4, 5x5, 6x6 scheint eine Stunde GPU einige interessante Ergebnisse zu liefern.

Chad Brewbaker

Beweise, dass die Matrixmultiplikation in quadratischer Zeit durchgeführt werden kann?

Antworten: