Pytania otagowane jako matrix-product

4
Dowody na to, że mnożenie macierzy można przeprowadzić w czasie kwadratowym?
Powszechnie przypuszcza się, że , optymalny wykładnik mnożenia macierzy, w rzeczywistości jest równy 2. Moje pytanie jest proste:ωω\omega Jakie mamy powody, by sądzić, że ?ω=2ω=2\omega = 2 Mam świadomość szybkich algorytmów, takich jak Coppersmith-Winograd, ale nie wiem, dlaczego można je uznać za dowód na .ω=2ω=2\omega = 2 Naiwnie wydaje mi …
1
Złożoność obliczeniowa mnożenia macierzy
Szukam informacji o złożoności obliczeniowej mnożenia macierzy prostokątnych macierzy. Wikipedia stwierdza, że ​​złożoność pomnożenia przez B ∈ R n × p wynosi O ( m n p ) (mnożenie podręcznika).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) Mam przypadek, w którym i n są znacznie mniejsze niż p , …
1
Pojemność jednoznacznie rozwiązanej układanki (USP)
W swoim kluczowym artykule Teoretyczne algorytmy grupowania macierzy Cohn, Kleinberg, Szegedy i Umans przedstawiają koncepcję unikatowej układanki (zdefiniowanej poniżej) i zdolności USP. Twierdzą oni, że Coppersmith i Winograd, w ich własnym papierze przełomowy Mnożenie macierzy poprzez ciąg arytmetyczny , „pośrednio” udowodnić, że zdolność USP jest 3/22/33/22/33/2^{2/3} . Twierdzenie to zostało …
1
Mnożenie macierzy w
Szukałem mnożenia macierzy, więc najpierw odwiedziłem algorytmy mnożenia macierzy wiki. W referencjach znalazłem artykuł, który twierdzi, że używa algorytmu O ( n2)l o g( n ) )O(n2)losol(n))O(n^2 log(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go przeczytać, ale jeśli jest ktoś, kto czyta ten …
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ą …
2
Determinanty i mnożenie macierzy - podobieństwo i różnice w złożoności algorytmicznej i wielkości obwodu arytmetycznego
Próbuję zrozumieć związek między złożonością algorytmiczną a złożonością obwodów determinant i mnożenia macierzy. Wiadomo, że wyznacznik macierzy można obliczyć w czasie , gdzie to minimalny czas wymagany do pomnożenia dowolnych dwóch macierzy. Wiadomo również, że najlepszą złożonością obwodów wyznaczników jest wielomian na głębokości i wykładniczy na głębokości 3. Ale złożoność …
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.