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.)
Antworten:
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
quelle