Frage:
Gibt es eine etablierte Prozedur oder Theorie zum Erzeugen von Code, die eine Matrix-Vektor-Multiplikation effizient anwendet, wenn die Matrix dicht ist und nur mit Nullen und Einsen gefüllt ist? Im Idealfall würde der optimierte Code systematisch auf zuvor berechnete Informationen zurückgreifen, um Doppelarbeit zu reduzieren.
Mit anderen Worten, ich habe eine Matrix und möchte eine Vorberechnung auf der Grundlage von , um so effizient wie möglich zu berechnen , wenn ich später den Vektor erhalte .
ist eine rechteckige dichte binäre Matrix, die zur "Kompilierzeit" bekannt ist, während ein unbekannter reeller Vektor ist, der nur zur "Laufzeit" bekannt ist.
Beispiel 1: (Schiebefenster)
Lassen Sie mich ein einfaches kleines Beispiel verwenden, um meinen Standpunkt zu veranschaulichen. Betrachten Sie die Matrix Angenommen, wir wenden diese Matrix auf einen Vektor an, um w = Mv zu erhalten . Dann lauten die Einträge des Ergebnisses \ begin {align} w_1 & = v_1 + v_2 + v_3 + v_4 + v_5 \\ w_2 & = v_2 + v_3 + v_4 + v_5 + v_6 \\ w_3 & = v_3 + v_4 + v_5 + v_6 + v_7 \\ w_4 & = v_4 + v_5 + v_6 + v_7 + v_8 \ end {align}
Wenn Sie eine Standardmatrix-Vektor-Multiplikation durchführen, wird genau dies berechnet. Ein Großteil dieser Arbeit ist jedoch überflüssig. Wir könnten die gleiche Matrixberechnung zu geringeren Kosten durchführen, indem wir eine "laufende Summe" verfolgen und addieren / subtrahieren, um die nächste Zahl zu erhalten:
Beispiel 2: (hierarchische Struktur)
Im vorherigen Beispiel konnten wir nur eine laufende Summe verfolgen. Normalerweise müsste jedoch ein Baum mit Zwischenergebnissen erstellt und gespeichert werden. Angenommen,
- Berechnen Sie und und addieren Sie sie, um w_3 zu erhalten .
- Berechnen Sie und und addieren Sie sie, um w_2 zu erhalten .
- Addiere und , um zu erhaltenw 3 w 1
Die Struktur in den obigen Beispielen ist leicht zu sehen, aber für die tatsächlichen Matrizen, die mich interessieren, ist die Struktur nicht so einfach.
Beispiel 3: (niedriger Rang)
Um einige Verwirrungen zu beseitigen, sind die Matrizen im Allgemeinen nicht spärlich. Insbesondere muss eine Methode, die dieses Problem löst, in der Lage sein, effiziente Methoden zum Anwenden von Matrizen zu finden, bei denen große Blöcke mit Einsen gefüllt sind. Zum Beispiel betrachten
Diese Matrix kann als Differenz zweier Rang-1-Matrizen zerlegt werden,
so seine Wirkung auf einem Vektor berechnet werden kann effizient durch, w 1
Motivation:
Ich arbeite an einer numerischen Methode für einige Bildverarbeitungen, und es gibt mehrere große dichte Matrizen mit unterschiedlichen Strukturen, die für alle Zeiten festgelegt sind. Später müssen diese Matrizen auf viele unbekannte Vektoren angewendet werden , die von der Eingabe des Benutzers abhängen. Im Moment benutze ich Bleistift und Papier, um einen effizienten Code pro Matrix zu erstellen, aber ich frage mich, ob der Prozess automatisiert werden kann.v i
Bearbeiten: (Nachschrift)
Alle Antworten hier (Stand 05.09.15) sind interessant, aber keine beantwortet die Frage so zufriedenstellend, wie ich es mir erhofft hatte. Wahrscheinlich stellt sich heraus, dass dies eine schwierige Forschungsfrage ist und niemand eine gute Antwort kennt.
Da die Zeit abgelaufen ist, gewähre ich der Antwort von EvilJS das Kopfgeld, da es die richtige Frage anspricht. Ich wünsche mir jedoch, dass die Antwort klarere und detailliertere Erklärungen enthält.
Die Antwort von tranisstor stellt eine Verbindung zwischen dieser Frage und dem Online Boolean Matrix-Vector Multiplication (OMv) -Problem her, aber die Verbindung ist nicht genau das, was diese Frage stellt. Insbesondere passt die folgende Annahme nicht wirklich (fett hervorgehoben meine),
Nehmen wir nun an, dass wir für alle und alle Matrizen n × n einen Algorithmus , der für alle Vektoren in wirklich subquadratischer Zeit berechnet , dh in Zeit für einige .
Ob für alle Matrizen subquadratische Algorithmen existieren oder nicht, ist orthogonal zur Frage, ob ein Algorithmus für eine bestimmte Matrix gefunden werden soll, der so schnell wie möglich ist. Die meisten 0-1-Matrizen sehen aus wie zufälliges Rauschen und haben (wenn ich raten würde) wahrscheinlich keine subquadratischen Algorithmen. Die Tatsache, dass es wirklich schlechte Matrizen gibt, hindert mich jedoch nicht daran, einen schnellen Algorithmus für eine gute Matrix zu finden, beispielsweise eine "Schiebefenster" -Matrix.
Die Antworten von vzn, die erste Antwort und die zweite Antwort sind interessant (und meiner Meinung nach verdienen sie nicht so viele Abwertungen), gelten jedoch aus den in den Kommentaren genannten Gründen nicht für die Frage.
quelle
Antworten:
Wenn es möglich ist, versuchen Sie, die bandierte tridiagonale Natur der Matrix auszunutzen.
Wenn die Matrix nur eine konstante Anzahl unterschiedlicher Werte enthält (was sicherlich binär ist), sollten Sie den Mailman-Algorithmus (von Edo Liberty, Steven W. Zucker, Technischer Bericht der Universität Yale Nr. 1402) ausprobieren: Über endliches Wörterbuch optimiert
Common Subexpression Elimination ist seit einiger Zeit bekannt als Multiple Constant Multiplication, aber das Herunterschalten auf Gate-Ebene ist eine Option - die hier verwendeten Muster können separat als Lösung verwendet oder mit anderen Methoden zusammengeführt werden, dem Artikel zur "Verbesserung der Common Subexpression Elimination" Algorithmus mit einem neuen Verzögerungsberechnungsverfahren auf Gate-Ebene "von Ning Wu, Xiaoqiang Zhang, Yunfei Ye und Lidong Lan, veröffentlicht in" Proceedings of the World Congress on Engineering and Computer Science 2013, Band II WCECS 2013, 23.-25. Oktober 2013, San Francisco, USA " Gate-Ebene CSE
Es gibt auch eine grobe, aber funktionierende Methode, um eine symbolische Matrix mit Konstanten zu generieren, einen Vektor mit Variablen zu erstellen und diese von Compilern an Static Single Assingment (SSA) anzuschließen, wodurch der Prozess des Schreibens von Matrizen von Hand automatisiert wird.
Neuer Algorithmus-Prototyp
Was Sie mit der laufenden Summe gemacht haben: Gibt 10 Operationen , und mit meiner anfänglichen Idee, Thomas zu verwenden, ist es äquivalent. Im Moment schreibe und teste ich immer noch neue Algorithmen, auch die Laufzeiten sind unangenehm , aber das erste Testergebnis gab mir eine überraschende Antwort:
Gibt 9 Operationen aus und definiert sie als + oder - ist 1 und = ist 0.
Dies ergibt 7 Operationen , mein Algorithmusergebnis ergibt: Das gibt 6 Operationen. Im Moment kann ich sagen, dass ich Hamming distance verwende, & und | bitweise Operationen, Zählen von Verwendungen und Erstellen von so etwas wie Cocke-Younger-Kasami (CYK) - "ein Parsing-Algorithmus für kontextfreie Grammatiken, benannt nach seinen Erfindern John Cocke, Daniel Younger und Tadao Kasami. Er verwendet Bottom-Up-Parsing und Dynamik Programmierung." - aus Wikipedia Dies ist die gleiche Technik, die ich zum Erstellen von Variablenblöcken verwende.
quelle
Dies hängt mit einer offenen Forschungsfrage zusammen, die als "Online Boolean Matrix-Vector Multiplication (OMv) -Problem" bekannt ist. Dieses Problem lautet wie folgt (siehe [1]): Wenn eine binäre Matrix und binäre Spaltenvektoren , müssen wir berechnen, bevor ankommt.M n v 1 , … , v n M v i v i + 1n×n M n v1,…,vn Mvi vi+1
Beachten Sie, dass das Problem aus der Frage etwas allgemeiner ist: Es erlaubt Matrizen und reelle Vektoren. Beachten Sie, dass das Problem mit Matrizen und Booleschen Vektoren "einfacher" ist, da es einen Sonderfall darstellt.n × nm×n n×n
Offensichtlich benötigt der naive Algorithmus für das Online-Boolesche Matrix-Vektor-Multiplikationsproblem (das nur die Standard-Matrix-Vektor-Multiplikation verwendet) die Zeit . Es gibt eine Vermutung (siehe zB [1]), dass dies nicht wirklich schneller als . (Im Einzelnen lautet diese Vermutung wie folgt: Es gibt keinen wirklich subkubischen Algorithmus, der das Online-Boolesche Matrix-Vektor-Multiplikationsproblem löst, dh es gibt keinen Algorithmus mit der Laufzeit für ).O ( n 3 ) O ( n 3 - & egr ; ) & egr ; > 0O(n3) O(n3) O(n3−ε) ε>0
Es ist bekannt, dass Williams Algorithmus dieses Problem in der Zeit löst . Siehe [2] für weitere Details.O(n3/log2n)
Es wäre ein Durchbruch im Bereich der bedingten Untergrenzen, wenn man die obige Vermutung beweisen oder widerlegen könnte.
[1] Vereinheitlichen und Verstärken der Härte für dynamische Probleme über eine Online-Matrix-Vektor-Multiplikations-Vermutung. von Henzinger, Krinninger, Nanongkai und Saranurak
[ http://eprints.cs.univie.ac.at/4351/1/OMv_conjecture.pdf ]
[2] Matrix-Vektor-Multiplikation in subquadratischer Zeit: (Vorverarbeitung erforderlich). von Williams
[ http://dl.acm.org/citation.cfm?id=1283383.1283490 ]
Aktualisieren
Eine der Fragen in den Kommentaren lautete wie folgt: Wir kennen zur Kompilierungszeit. Können wir unseren Algorithmus nicht an anpassen , sodass das OMv-Problem (Vermutung) nicht zutrifft? Wir werden sehen, dass dies nicht der Fall ist, es sei denn, die OMv-Vermutung schlägt fehl.MM M
Die Beweisidee ist einfach: Nehmen wir an, wir könnten schnelle Algorithmen für alle Matrizen bis zu einer bestimmten Größe liefern (z. B. alle möglichen Fälle unterscheiden). Nach dieser bestimmten Größe verwenden wir Teilen und Erobern.
Hier sind die Details:n0∈N n≤n0 n×n M An,M v Mv O(n2−ε) ε>0 n0×n0
Fixiere einige , was (ohne Verlust der Allgemeinheit) eine Potenz von 2 und größer als 2 ist. Nun nehme an, dass für alle und alle Matrizen Wir kennen einen Algorithmus , der für alle Vektoren in einer wirklich subquadratischen Zeit berechnet , dh in der Zeit für einige . (Beachten Sie, dass dies einen individuellen Algorithmus für jede Matrix bis zur Größe .)
Nun werden wir OMv in wirklich subkubischer Zeit lösen:M n×n n=2k k n>n0 M M1,M2,M3,M4 2k−1×2k−1 2k−1≤n0 A2k−1,Mi n0
Wenn wir eine binäre Matrix der Größe mit für einige und , verwenden wir eine Divisions- und Eroberungsstrategie. Wir teilen in vier Untermatrizen der Größen . Wenn , verwenden wir den Algorithmus , andernfalls nehmen wir eine Rekursion vor. (Da eine feste Zahl ist, können wir den richtigen Algorithmus in konstanter Zeit auswählen.)
Beachten Sie, dass wir höchstens Rekursionsschritte benötigen . Außerdem werden wir für Vektoren Berechnungen durchführen. Um alle Matrix-Vektor-Multiplikationen zu verarbeiten, benötigen wir also eine Gesamtberechnungszeit von .O(logn) n v1,…,vn n O(n3−εlogn)
Es ist bekannt, dass der Logarithmus langsamer wächst als jedes Polynom (insbesondere langsamer als jede Wurzel). Fixing einig mit , wir sehen , dass unsere Gesamtberechnung in wirklich subcubic Laufzeit (insbesondere in der Zeit ). Somit wäre die OMv-Vermutung falsch.ε~>0 ε~<ε O(n3−ε~)
(Wenn die Größe und und keine Potenzen von 2 sind, gelten immer noch die Grenzen der Laufzeiten, da wir nur und auf die nächsten Potenzen von 2 erhöhen könnten .)M m×n m n n m
Schlussfolgerung: Wenn Sie Groß- und Kleinschreibung in den Eingabematrizen verwenden könnten, um schnelle Algorithmen abzuleiten, könnten Sie die OMv-Vermutung verbessern.
quelle
Hierbei handelt es sich im Wesentlichen um CS auf Forschungsniveau. Das Problem wird in mindestens zwei Formen untersucht, und zwar in Form der Multiplikation von dünnen Matrizen (Beispielpapier, das gerade zitiert wurde). Außerdem wird der Spezialfall der "binären dünnen Matrizen" untersucht. Es ist bekannt, dass der zweite Fall mit der Optimierung von linearen Programmen zusammenhängt. Minimale Programme können auch wie DAGs mit zwei Arten von "Gattern" sein, Addition und Multiplikation, so dass einige Literatur zur Schaltungsminimierung damit in Verbindung gebracht werden kann und möglicherweise Software "von der Stange" für diesen Zweck angepasst werden könnte. hier ist eine spezifische ref am 2 nd Fall und auch die gleiche Frage auf cstheory mit einiger grundlegenden ersten empirischen Studie.
Darstellung von spärlichen binären Matrizen als geradlinige Programme für die schnelle Matrix-Vektor-Multiplikation / Neves, Araujo
Schnelles spärliches boolesches Matrixkettenprodukt / -theorie
quelle
Ich bin nicht sicher, ob dieses Problem genau untersucht wurde, aber diese Forschung ist verwandt und scheint ein vernünftiger Anhaltspunkt zu sein. es befasst sich mit der Hypergraph-Zerlegung für die Multiplikation mit dünner Matrix. binäre Matrizen sind ein Sonderfall dieses Ansatzes. Dieser Ansatz findet optimalere Strategien als die "gerade" Multiplikationsmethode. Weitere Optimierungen (innerhalb dieses Rahmens) sind möglicherweise basierend auf der Eigenschaft der binären Matrix möglich.
quelle