Szybki rzadki produkt typu boolean z możliwym przetwarzaniem wstępnym

Jakie są najbardziej efektywne algorytmy mnożenia dwóch bardzo rzadkich macierzy boolowskich (powiedzmy, N = 200, a jest tylko około 100-200 niezerowych elementów)?

W rzeczywistości mam tę zaletę, że kiedy mnożę A przez B, B są predefiniowane i mogę na nich dowolnie skomplikowane przetwarzanie wstępne. Wiem też, że wyniki produktów są zawsze tak rzadkie jak oryginalne matryce.

Algorytm „raczej naiwny” (skanowanie A po wierszach; dla każdego 1 bitu rzędu A LUB wynik z odpowiednim rzędem B) okazuje się bardzo wydajny i wymaga tylko kilku tysięcy instrukcji CPU do obliczenia pojedynczego produktu , więc nie będzie łatwo go przekroczyć, a da się go pokonać tylko przez stały współczynnik (ponieważ w wyniku są setki jednych bitów). Ale nie tracę nadziei i proszę społeczność o pomoc :)

— jkff
źródło

Wątpię, czy możemy znacznie pobić stałą 10 instrukcji maszynowych na słowo wyjściowe. Czy to możliwe, że jakaś domniemana forma wyniku byłaby do przyjęcia?

— Warren Schudy,

Tak, o ile można go jeszcze pomnożyć przez Bs.

— jkff,

Jakie są operacje dodawania i mnożenia (dla bitów), na podstawie których definiowane jest mnożenie macierzy? Twój naiwny algorytm sugeruje, że odpowiedzią jest odpowiednio „lub” i „i”, ale jest to dość dziwne mnożenie macierzy, ponieważ nie definiują one pola. Czy masz na myśli „xor” zamiast „lub”?

— Warren Schudy,

Nie, mam na myśli „lub” i „i”. Nie potrzebuję operacji do zdefiniowania pola, to właściwie problem podobny do osiągalności wykresu (obliczam skład kilku funkcji jeden do wielu).

— jkff,

Odpowiedzi:

Nie chciałem na to odpowiadać, ponieważ mój jedyny wynik teoretyczny, jaki znam, jest na papierze ...

$n \times n$ $A$ $A$ $n$

(Uwaga: ten algorytm jest naprawdę użyteczny tylko w przypadku, gdy jedna matryca jest gęsta, a druga jest rzadka. Ten przypadek pojawia się często, np. Podczas obliczania przejściowego zamknięcia rzadkiego wykresu macierz przechodniego przechodzenia w końcu będzie gęsta w porównaniu do oryginalnej macierzy przylegania).

Papier jest

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams: Nowe podejście kombinatoryczne do problemów z rzadkimi grafami. ICALP (1) 2008: 108–120

$\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})$

Wykorzystaliśmy tę strukturę danych, aby uzyskać szybsze algorytmy teoretyczne dla APSP w rzadkich nieważonych grafach.

— Ryan Williams
źródło

Właśnie zauważyłem, że zakładasz również, że wynik mnożenia macierzy jest również rzadki. W takim przypadku istnieją jeszcze szybsze algorytmy; przeprowadź wyszukiwanie w Internecie pod kątem „mnożenia macierzy wrażliwej na wyniki”.

— Ryan Williams

{- 1, 0, 1}

$\{-1, 0, 1\}$

Myślę, że to, co nazywacie, to macierz „hipersparse” (nnz <n). Kilka lat temu napisałem artykuł na temat ich pomnożenia. Zasadniczo jest to połączenie produktu zewnętrznego ze sprytnym połączeniem na wiele sposobów, aby wyeliminować realizację potrójnych pośrednich.

Buluc and Gilbert, IPDPS 2008: http://gauss.cs.ucsb.edu/publication/hypersparse-ipdps08.pdf

— Aydin Buluc
źródło