Wie lässt sich die Anzahl der Nicht-Nullen bei der Multiplikation mit dünner Matrix am besten bestimmen?

17

Ich habe mich gefragt, ob es eine schnelle und effiziente Methode gibt, um die Anzahl der Nicht-Nullen im Voraus für die Sparse-Matrix-Multiplikationsoperation zu ermitteln, vorausgesetzt, beide Matrizen sind im CSC- oder CSR-Format.

Ich weiß, dass es ein smmp-Paket gibt, aber ich benötige etwas, das bereits in C oder C ++ implementiert ist.

Jede Hilfe wird geschätzt. Danke im Voraus.

Recker
quelle
Haben Ihre Matrizen eine Symmetrie oder eine Struktur zum Ort ihrer Nicht-Null-Einträge?
Godric Seer
@GodricSeer ... nein, ich spreche nur über allgemeine spärliche Matrizen. Matlab hat nnz (A), wobei A eine spärliche Matrixmethode ist, um die Anzahl der Nicht-Nullen herauszufinden. Ich habe mich gefragt, ob es eine solche Methode gibt.
Recker
Ich persönlich kann mir keine Methode vorstellen, um diese Zahl zu berechnen, die niedriger wäre als die tatsächliche Matrixmultiplikation, ohne Symmetrie oder Struktur auszunutzen. Ich gehe davon aus, dass Sie dies für die Speicherzuweisung vor der Multiplikation wollen?
Godric Seer
Außerdem habe ich dieses Papier gefunden, in dem beschrieben wird, wie die Anzahl eines Booleschen Matrixprodukts geschätzt wird (was mit dem Zählen der Elemente in einem Matrixprodukt identisch ist).
Godric Seer
@ GodricSeer..Ja, Sie haben recht, ich brauche die genaue Nummer nur für die Speicherzuweisung der resultierenden Matrix. Danke für den Link zu Papier. Das könnte mich für eine Weile in eine Richtung bringen.
Recker

Antworten:

14

Sie können das Matrix-Matrix-Produkt einfach simulieren, indem Sie das Produkt der beiden Sparsity-Muster bilden. Das heißt, Sie betrachten das Sparsity-Muster (das in separaten Arrays im CSR-Format gespeichert ist) als Matrix, die entweder eine Null oder eine Eins enthält jeder Eintrag. Für die Ausführung dieses simulierten Produkts müssen Sie nur das und bildenDie Operation mit diesen Nullen und Einsen ist also viel schneller als das eigentliche Matrix-Matrix-Produkt. Sie müssen lediglich die Zeilen und Spalten der beiden Matrizen durchgehen und sicherstellen, dass in a mindestens ein Eintrag vorhanden ist Zeile und die Spalte, mit der multipliziert wird, wobei beide Matrizen ungleich Null sind. Dies ist eine billige Operation - auf jeden Fall viel billiger als die eigentliche Gleitkommamultiplikation im eigentlichen Produkt, die nicht nur Gleitkomma-Arithmetik (teuer) erfordert, sondern auch das Einlesen der tatsächlichen Gleitkommazahlen aus dem Speicher ( noch teurer, aber das brauchen Sie nicht, wenn Sie das Sparsity-Muster multiplizieren, weil die Nicht-Null-Werte der Matrix separat im CSR gespeichert werden.

Wolfgang Bangerth
quelle
6
Dies nennt man symbolische Multiplikation. Dies ist nicht unbedingt günstiger als die numerische Multiplikation, insbesondere bei paralleler Multiplikation. Sie muss jedoch nur einmal pro Sparsity-Muster durchgeführt werden. Viele Algorithmen führen die Operation mehrmals mit unterschiedlichen numerischen Werten aus, jedoch mit demselben Sparsity-Muster. In diesem Fall kann die symbolische Multiplikation wiederverwendet werden.
Jed Brown
Es ist eine gute Idee, aber angesichts der Millionen von Transistoren, die das Float * Float parallel ausführen, sprechen wir hier nur von einer Geschwindigkeitseinsparung von 50% oder etwa 50%.
Evgeni Sergeev
1
@EvgeniSergeev - es geht nicht um Einsparungen bei den Berechnungen, sondern um Einsparungen bei der Speicherübertragung. Da Sie heute 80% oder mehr Zeit für die Speicherübertragung für eine Multiplikation mit dünner Matrix aufwenden, gewinnen Sie wahrscheinlich erheblich, wenn Sie keine Gleitkommadaten aus dem / in den Speicher lesen / schreiben müssen.
Wolfgang Bangerth
CmkÖ(mk)
Ö(mk)pm=kÖ(mpLogp)Ö(m2)
13

Ich habe tatsächlich den Originalcode in Matlab für A * B geschrieben, sowohl für A als auch für B sparsam. Die Vorbelegung des Platzes für das Ergebnis war in der Tat der interessante Teil. Wir haben beobachtet, worauf Godric hinweist: Die Anzahl der Nonzeros in AB zu kennen, ist genauso kostspielig wie AB zu berechnen.

Wir haben die erste Implementierung von spärlichem Matlab um 1990 durchgeführt, bevor das Edith-Cohen-Papier die erste praktische und schnelle Möglichkeit bot, die Größe von AB genau abzuschätzen. Wir haben einen Schätzer für eine minderwertige Größe zusammengestellt und, wenn uns während der Berechnung der Speicherplatz ausgeht, die Zuordnung verdoppelt und das teilweise berechnete Ergebnis kopiert.

Ich weiß nicht, was jetzt in Matlab ist.

Eine andere Möglichkeit wäre, AB spaltenweise zu berechnen. Jede Spalte kann vorübergehend in einem Akkumulator mit geringer Dichte gespeichert werden (eine Erklärung hierzu finden Sie im Matlab-Papier mit geringer Dichte). Der zugewiesene Speicherplatz enthält die genau bekannte Größe der Ergebnisspalte. Das Ergebnis wäre eine verstreute, komprimierte, dünn besetzte Spaltenform - jede Spalte in CSC, aber keine Intercolumn-Kontiguität - unter Verwendung von 2 Vektoren der Länge numcols (Spaltenanfang, Spaltenlänge) anstelle von einem als Metadaten. Es ist eine Speicherform, die einen Blick wert sein kann; Es hat eine weitere Stärke: Sie können eine Spalte vergrößern, ohne die gesamte Matrix neu zuzuweisen.

Rob Schreiber
quelle
Gut für meine GPU-Implementierung, fand ich zuerst die Nicht-Null-Struktur und dann die eigentliche Matrix. Die Leistung war erwartungsgemäß schrecklich. Ich denke, sie verwenden die in diesem Buch beschriebene Methode, um die beiden spärlichen Matrizen in MATLAB effizient zu multiplizieren.
Recker
2
Wirklich cool, danke für die historische Perspektive und willkommen bei scicomp :)
Aron Ahmadia
4

Diese Arbeit beschreibt einen Algorithmus zur Approximation der Größe einer Resultierenden aus dem Matrixprodukt zweier dünn besetzter Matrizen.

Das Problem beim Finden einer exakten Anzahl von Nicht-Null-Einträgen in einer Multiplikation mit einer dünnen Matrix besteht darin, dass jedes Element in der Resultierenden von der Wechselwirkung zweier Vektoren abhängt, von denen beide wahrscheinlich mindestens einige Nicht-Null-Elemente enthalten. Um die Anzahl zu berechnen, müssen Sie logische Operationen für ein Vektorpaar für jedes Element in der Ergebnismenge auswerten. Das Problem dabei ist, dass eine Anzahl von Operationen erforderlich ist, die der Anzahl der Operationen entspricht, die zum Berechnen des Matrixprodukts selbst erforderlich sind. In meinen Kommentaren erwähnte ich die Möglichkeit, bestimmte Strukturen in den Nicht-Null-Elementen der ursprünglichen Matrizen auszunutzen, jedoch könnten dieselben Exploits auch dazu verwendet werden, die bei der Matrixmultiplikation geleistete Arbeit zu reduzieren.

Es ist wahrscheinlich besser, das obige Papier zu verwenden, um den Speicherbedarf zu überschätzen, die Multiplikation durchzuführen und dann den zugewiesenen Speicher abzuschneiden oder die resultierende Matrix in ein Array mit geeigneterer Größe zu verschieben. Auch dünn besetzte Matrixprodukte sind keine Seltenheit, und ich würde fast garantieren, dass dieses Problem bereits gelöst wurde. Wenn Sie sich ein wenig mit Open Source-Bibliotheken mit spärlicher Matrix beschäftigen, sollten Sie sich mit den Algorithmen befassen, mit denen sie Speicher vorbelegen.

Godric Seher
quelle
0

Haben Sie bei CSR oder CSC die Garantie, dass Ihr Array von Matrixelementen bereits keine Nullen enthält? In diesem Fall ist es einfach herauszufinden, wie viele Nicht-Null-Elemente es gibt, und zwar mit etwas ähnlichem wie:

int nnz = sizeof(My_Array)/sizeof(long int);

Wenn dies jedoch nicht der Fall ist (scheint ein bisschen zu einfach zu sein), können Sie eine Reduzierung versuchen . Wenn Ihr Array von Matrixelementen sehr groß ist, ist dies möglicherweise die effizienteste Methode, um die Anzahl der Elemente ungleich Null zu berechnen. Viele parallele C / C ++ - Bibliotheken wie Thrust (eine CUDA-Bibliothek) oder OpenCL (für deren Verwendung Sie keine GPU benötigen) unterstützen bedingte Reduktionen. Fügen Sie für jedes Element das Ergebnis von hinzu Condition(Element). Wenn Sie die Bedingung auf setzen Element != 0, addieren Sie die Anzahl der Elemente ungleich Null. Möglicherweise möchten Sie auch die Elemente mit dem Wert Null aus Ihrem Array von Elementen, dem Array von Zeilen- / Spaltenindizes entfernen und Ihre Spalten- / Zeilenzeiger anpassen.

Zitronen
quelle
Vielen Dank für Ihre Antwort ... aber ich bezog mich auf Nicht-Nullen in A * B, wo A und B spärliche Matrizen sind. Ich benötige die Anzahl der Nicht-Nullen im Voraus, damit ich die genaue Speichermenge zum Speichern der resultierenden Matrix zuweisen kann.
Recker
0

Die einfachste Möglichkeit zur Implementierung von CSR ist der Versuch

std::vector< std::map<int, complex<float>> > 

um deine Matrix darzustellen. In diesem Fall kümmern Sie sich nicht wirklich um die Anzahl der Nicht-Null-Elemente. Auf alle wird über zugegriffen

std::map< int, complex<float> >::iterator

in jeder Reihe. Beste ..


quelle
2
STL, als Sie dachten, dass Ihre Routinen mit spärlicher Matrix nicht langsamer sein könnten.
Jed Brown