Schnelles, dünnflüssiges Boolesches Matrixkettenprodukt

13

Ich habe also ungefähr 100-200 sehr spärliche quadratische boolesche Matrizen mit einer Seitenlänge von mehreren Dutzend, und ich muss ihr Produkt berechnen. Ich weiß, dass, wenn ich sie seriell multipliziere, das Produkt normalerweise bei jedem Schritt so dünn bleibt.

Gibt es in diesem Fall Algorithmen für Matrixkettenprodukte, die besonders schnell arbeiten?

Auf einer höheren Ebene besteht das Problem darin, die Zusammensetzung einer Reihe von Eins-zu-Viele-Zuordnungen in einem relativ kleinen Diagramm (Übergangsfunktionen eines NFA) zu berechnen, in dem die meisten Elemente nicht mehr als 0-3 entsprechen.

(Bitte beachten Sie, dass dies nicht das übliche "Matrixkettenprodukt" -Problem ist, da alle Matrizen dieselbe Größe haben und ich nicht die optimale Klammerung wählen muss.)

jkff
quelle
5
Tatsächlich kann die Reihenfolge, in der Sie sie multiplizieren, die Sparsamkeit der Zwischenergebnisse beeinflussen, sodass dies in einem solchen schnellen Algorithmus immer noch ein wichtiges Problem sein kann.
Joshua Grochow
Aus Ihrer anderen Frage, bei der Sie anscheinend 0/1 semiring AND / OR-Operationen verwenden, nicht Addition / Multiplikation (wie das Problem zu besagen scheint), machen Sie dies bitte in der Frage deutlich
vzn

Antworten:

10

Dies war zu lang, um einen Kommentar abzugeben - ich frage mich, ob diese Matrizen eine Struktur haben, die sie dazu bringt, sich anders zu verhalten als zufällige Matrizen. Produkte von zufälligen, spärlichen Matrizen gehen auf Null oder werden schnell nicht spärlich.

Hier ist ein einfaches Experiment: Nehmen Sie 200 zufällige binäre 50x50-Matrizen und zeichnen Sie die Anzahl der Nicht-Nullen in Abhängigkeit von der Anzahl der multiplizierten Matrizen. Die folgenden Darstellungen zeigen die Standardabweichung über 2000 Läufe. Erster Plot ist für 2% Sparsity, zweiter Plot ist für 3%


(Quelle: yaroslavvb.com ) (Quelle: yaroslavvb.com )

Dies dauerte 3 Minuten auf meinem Laptop mit Standard-Matrix-Multiplikation

Jaroslaw Bulatow
quelle