Pytania otagowane jako sparse-matrix

2
Skuteczne znajdowanie 5-cykli na rzadkim wykresie.
(crossposted z MathOverflow) Cześć, Czytałem ten wątek: /mathpro/16393/finding-a-cycle-of-fixed-length Chcę znaleźć 5-cykl na wykresie. Tak naprawdę to, czego naprawdę chcę, to najkrótszy nieparzysty cykl o długości co najmniej 5, ale może to trochę poza tym. Dla moich celów, traktuję i to samo w analizie złożoności. nmmmnnn Czy w takim przypadku możemy …
4
Znalezienie najrzadszego rozwiązania układu równań liniowych
Jak trudno jest znaleźć najrzadsze rozwiązanie układu równań liniowych? Bardziej formalnie, rozważ następujący problem decyzyjny: Instancja: układ równań liniowych o współczynnikach całkowitych i liczbie ccc . Pytanie: Czy istnieje rozwiązanie dla systemu z co najmniej ccc zmiennymi przypisanymi do zera? Próbuję również ustalić, na czym polega zależność od ccc . …
1
Szybki rzadki łańcuch boolowski z matrycą
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 …
2
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ą …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.