Schnelles, dünnflüssiges Boolesches Matrixprodukt mit möglicher Vorverarbeitung

12

Was sind die praktisch effizientesten Algorithmen zum Multiplizieren von zwei sehr spärlichen booleschen Matrizen (z. B. N = 200 und es gibt nur einige 100-200 Nicht-Null-Elemente)?

Eigentlich habe ich den Vorteil, dass beim Multiplizieren von A mit B die Bs vordefiniert sind und ich willkürlich komplexe Vorverarbeitungen an ihnen vornehmen kann. Ich weiß auch, dass die Ergebnisse von Produkten immer so spärlich sind wie die Originalmatrizen.

Der "ziemlich naive" Algorithmus (zeilenweises Abtasten von A; für jedes Bit der A-Reihe ODER das Ergebnis mit der entsprechenden Zeile von B) erweist sich als sehr effizient und erfordert nur ein paar tausend CPU-Anweisungen, um ein einzelnes Produkt zu berechnen Es wird also nicht einfach sein, es zu übertreffen, und es ist nur um einen konstanten Faktor übertreffbar (da das Ergebnis Hunderte von Ein-Bit-Werten enthält). Aber ich verliere nicht die Hoffnung und bitte die Community um Hilfe :)

jkff
quelle
1
Ich bezweifle, dass wir eine Konstante von 10 Maschinenbefehlen pro Ausgangswort deutlich schlagen können. Ist es möglich, dass eine implizite Form der Ausgabe akzeptabel ist?
Warren Schudy
Ja, solange es mit Bs weiter multipliziert werden kann.
jkff
Auf welchen Additions- und Multiplikationsoperationen (für Bits) basiert die Matrixmultiplikation? Ihr naiver Algorithmus schlägt vor, dass die Antwort "oder" und "und" ist, aber das ist eine ziemlich seltsame Matrixmultiplikation, da diese kein Feld definieren. Meinen Sie "xor" anstelle von "or"?
Warren Schudy
Nein, ich meine "oder" und "und". Ich brauche die Operationen nicht, um ein Feld zu definieren, das ist eigentlich ein Problem, das der Erreichbarkeit von Graphen ähnelt (ich berechne die Zusammensetzung mehrerer Eins-zu-Viele-Funktionen).
JKFF

Antworten:

11

Ich wollte das nicht beantworten, weil das einzige theoretische Ergebnis, das ich in dieser Richtung kenne, meinen Namen auf dem Papier hat ...

Theoretisch ist es möglich, eine dichte Boolesche Matrix A vorzuverarbeiten, so dass spärliche Matrix-Vektor-Multiplikationen mit A (über das Semiren von OR und AND) schneller als die naive Laufzeit durchgeführt werden können. Wahrscheinlich wäre eine erhebliche Menge an Hacking erforderlich, um es in der Praxis zu implementieren, aber ich denke, es würde sich in der Praxis als gut erweisen, wenn es groß genug für n und die richtige Implementierung wäre.n×nAAn

(Hinweis: Dieser Algorithmus ist nur dann wirklich nützlich, wenn eine Matrix dicht und die andere dünn ist. Dieser Fall tritt jedoch häufig auf, wenn z. B. das transitive Schließen eines dünnen Graphen berechnet wird, wird die transitive Schließungsmatrix schließlich dicht verglichen mit der ursprünglichen Adjazenzmatrix.)

Das Papier ist

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: Ein neuer kombinatorischer Ansatz für spärliche Graphprobleme. ICALP (1) 2008: 108 & ndash; 120

und das entsprechende Ergebnis aus dem Papier ist , dass für jedes gibt es eine O ( n 2 + ε ) Algorithmus dass für jeden n × n 0-1 Matrix A , werden die folgenden Vorgänge unterstützt:ε>0O(n2+ε)n×nA

vtAvO(n(t/k+n/)/logn)k(k)nε=logcnk=ε(logn)/loglognnt/logn+n2/logcnc

AO(n1+ε)

Wir haben diese Datenstruktur verwendet, um schnellere theoretische Algorithmen für APSP in spärlichen, ungewichteten Diagrammen zu erhalten.

Ryan Williams
quelle
3
Mir ist gerade aufgefallen, dass Sie auch davon ausgehen, dass die Ausgabe der Matrixmultiplikation ebenfalls spärlich ist. In diesem Fall gibt es noch schnellere Algorithmen. Führen Sie eine Websuche nach "ausgangssensitiver Matrixmultiplikation" durch.
Ryan Williams
{1,0,1}
4

Ich denke, was Sie nennen, ist eine "hypersparse" Matrix (nnz <n). Vor ein paar Jahren schrieb ich eine Arbeit darüber, wie man sie multipliziert. Im Wesentlichen handelt es sich dabei um eine äußere Produktverbindung mit einer cleveren Multi-Way-Zusammenführung, um die Realisierung von Intermediate-Tripeln zu vermeiden.

Buluc und Gilbert, IPDPS 2008: http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf

Aydin Buluc
quelle