Mam więc około 100-200 bardzo rzadkich kwadratowych macierzy boolowskich o długości boku ~ kilkudziesięciu i muszę obliczyć ich iloczyn. Wiem, że jeśli pomnożę je szeregowo, produkt zwykle pozostanie tak rzadki na każdym kroku.
Czy w tym przypadku są jakieś algorytmy łańcucha macierzy, które działają szczególnie szybko?
Na wyższym poziomie problemem jest obliczenie składu serii odwzorowań jeden do wielu na stosunkowo małym wykresie (funkcje przejściowe NFA), gdzie większość elementów odwzorowuje nie więcej niż 0-3.
(należy pamiętać, że nie jest to zwykły problem związany z „produktem łańcucha macierzy”, ponieważ wszystkie macierze mają ten sam rozmiar i nie muszę wybierać optymalnego nawiasowania)
5
w rzeczywistości kolejność ich pomnażania może wpływać na rzadkość wyników pośrednich, więc nadal może być ważnym problemem w każdym tak szybkim algorytmie.
—
Joshua Grochow
z drugiego pytania, które wydaje się, że używasz 0/1 do przerywania operacji AND / OR, a nie dodawania / mnożenia (jak wydaje się, że problem), proszę
—
wyjaśnij
