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

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 :)

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 \times n$$A$$A$$n$

(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:$\varepsilon > 0$$O(n^{2+\varepsilon})$$n \times n$$A$

$v$$t$$A v$$O(n(t/k + n/\ell)/\log n)$$\ell$$k$${\ell \choose k} \leq n^{\varepsilon}$$\ell=\log^c n$$k=\varepsilon(\log n)/\log \log n$$nt/\log n + n^2/\log^c n$$c$

$A$$O(n^{1+\varepsilon})$

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

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