Die rechnerische Komplexität der Matrixmultiplikation

Ich suche Informationen über die rechnerische Komplexität der Matrixmultiplikation von Rechteckmatrizen. Wikipedia besagt , dass die Komplexität der Multiplikation von ist (Schulbuch Multiplikation). $A \in \mathbb{R}^{m \times n}$ $B \in \mathbb{R}^{n \times p}$ $O(mnp)$

Ich habe einen Fall, in dem und viel kleiner als , und ich hatte gehofft, eine bessere Komplexität als linear in , auf Kosten der Verschlechterung der Abhängigkeit von und als linear. $m$ $n$ $p$ $p$ $m$ $n$

Irgendwelche Ideen?

Vielen Dank.

Anmerkung: Der Grund, von dem ich hoffe, dass es möglich ist, ist das bekannte Ergebnis einer Abhängigkeit von weniger als einer Kubikzahl in wenn (wenn Matrizen alle Quadrate sind). $p$ $m=n=p$

cc.complexity-theory time-complexity linear-algebra matrix-product Erkundiger
quelle

Die Komplexität eines (sequentiellen) Algorithmus kann nicht kleiner sein als die Größe seiner Ausgabe. Können Sie für Ihr Problem die Eingabe und Ausgabe mit dem in p sublinearen Raum darstellen?

Colin McQuillan

sind die elemente meist ungleich null oder oft null? dh spärlich? das führt sicher zu diversen optimierungen. es scheint auch, dass die SVD [Singularwertzerlegung] basierend auf der aktuellen Antwort, die sich auf Approximationen bezieht, relevant sein könnte.

vzn

Antworten:

Die klassische Arbeit von Coppersmith zeigt, dass man für einige eine Matrix mit einer Matrix in -Arithmetikoperationen multiplizieren kann . Dies ist ein wesentlicher Bestandteil des kürzlich gefeierten Ergebnisses von Ryan Williams. $\alpha > 0$ $n \times n^\alpha$ $n^\alpha \times n$ $\tilde{O}(n^2)$

François le Gall hat kürzlich die Arbeit von Coppersmith verbessert und seine Arbeit wurde gerade in das FOCS 2012 aufgenommen. Um diese Arbeit zu verstehen, benötigen Sie einige Kenntnisse in der algebraischen Komplexitätstheorie. Virginia Williams Papier enthält einige relevante Hinweise. Insbesondere die Arbeit von Coppersmith ist in dem Buch Algebraic Complexity Theory ( Algebraische Komplexitätstheorie) vollständig beschrieben .

Ein anderer Arbeitsbereich konzentriert sich auf die Multiplikation von Matrizen in etwa . Sie können diese Arbeit von Magen und Zouzias überprüfen. Dies ist nützlich für wirklich große Matrizen Handhabung, sagen wir eine Multiplikation - Matrix und eine Matrix, wobei . $n \times N$ $N \times n$ $N \gg n$

Der grundlegende Ansatz besteht darin, die Matrizen abzutasten (dies entspricht einer zufälligen Dimensionsreduktion) und die viel kleineren abgetasteten Matrizen zu multiplizieren. Der Trick besteht darin, herauszufinden, wann und in welchem Sinne dies eine gute Annäherung ergibt. Im Gegensatz zum bisherigen, völlig unpraktischen Arbeitsschritt sind Stichprobenalgorithmen praktisch und sogar für den Umgang mit großen Datenmengen erforderlich.

Yuval Filmus
quelle

Nur eine Anmerkung: Es ist bekannt (Stand November 2010), dass eine rechteckige Matrixmultiplikation für die Lösung von ACC SAT nicht erforderlich ist. (Was gut ist, weil rechteckige Matrix mult "galaktisch" und komplex ist.)

Ryan Williams