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)
Odpowiedzi:
To było zbyt długo, aby być komentarzem - zastanawiam się, czy te matryce mają strukturę, która sprawia, że zachowują się inaczej niż przypadkowe matryce. Produkty losowych macierzy rzadkich zbliżają się do zera lub szybko stają się rzadkie.
Oto prosty eksperyment - weź 200 losowych binarnych macierzy 50 x 50 i narysuj liczbę niezerowych w funkcji liczby macierzy pomnożonych. Poniższe wykresy pokazują odchylenie standardowe dla 2000 przebiegów. Pierwszy wykres dotyczy 2% rzadkości, drugi wykres dotyczy 3%
(źródło: yaroslavvb.com ) (źródło: yaroslavvb.com )
zajęło mi to 3 minuty na moim laptopie przy użyciu standardowego mnożenia macierzy
źródło