Mnożenie macierzy w

13

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)losol(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go przeczytać, ale jeśli jest ktoś, kto czyta ten artykuł lub wie o tym algorytmie, czy to prawda? i czy wiesz o podstawowej idei tego, aby to trochę opisać.

Z góry dziękuję, wiem, że to trochę ogólne pytanie, ale jeśli znalazłem dobre podejście, poznam szczegóły.

ds.algorithms linear-algebra matrix-product Saeed
źródło
5
Myślę, że warto lepiej zrozumieć własne pytanie. Szukasz algorytmu sekwencyjnego lub algorytmu równoległego? Nie są znane sekwencyjne algorytmy mnożenia macierzy z czasem O (n ^ 2 log n), a praca Ewy jest częściowym wynikiem w kierunku takich algorytmów (nie przeczytałem pracy, po prostu ją przejrzałem). Jeśli zależy ci na czasie równoległym, to czas równoległy O (log n) (przy założeniu dodawania skalarnego i mnożenia skalarnego w stałym czasie) jest standardem i można znaleźć wyjaśnienie np. W książce Computational Complexity autorstwa Papadimitriou.
Tsuyoshi Ito
2
(1) Edytuj swoje pytanie, aby było jasne, że pytasz o algorytmy sekwencyjne. (2) Zrozumiałem, że dodałeś tag [obliczenia kwantowe]. Edytuj swoje pytanie, aby wyjaśnić związek z obliczeniami kwantowymi. (Domyślam się, że twoje pytanie jest motywowane obliczeniami kwantowymi, ale twoje własne wyjaśnienie jest o wiele bardziej przydatne niż jakiekolwiek przypuszczenia.)
Tsuyoshi Ito
2
Zalecam najpierw usunięcie tego pytania, a następnie opublikowanie go później, jeśli okaże się, że masz pytanie.
Suresh Venkat
3
@Saeed: Ten problem został omówiony w meta i obecnie jest to polityka witryny, jeśli chcesz omówić zasady, użyj meta. Z drugiej strony możesz zmodyfikować pytanie i unikać wspominania o pracy, aby była ona tematyczna, np. Modyfikując pytanie, aby stało się „jaki jest najbardziej znany algorytm mnożenia macierzy w modelu X?”. i to byłoby na temat. (uwaga: jeśli nie możesz sam zweryfikować poprawności niepublikowanego artykułu i chcesz go zacytować, zaczekaj, aż zostanie on przejrzany i opublikowany).
Kaveh
3
Powiązana dyskusja na temat Meta: Czy można pytać o poprawność wydruków wstępnych na tematy przyjazne dla korb? Nie twierdzę, że wszystko, co napisano na tej stronie, będzie dotyczyło tego pytania, ale przynajmniej jest ściśle powiązane.
Tsuyoshi Ito

Odpowiedzi:

34

Natknąłem się na ten artykuł około rok temu, ale nie zacząłem go uważnie czytać. Mogę powiedzieć, że nie uważa się tego podejścia za prawidłowe. Na stronie 36 tego samego artykułu znajduje się komentarz Don Knutha, który wskazuje na poważną wadę tego podejścia.

Aby zrozumieć ten artykuł, musisz nauczyć się algebry grupowej i teorii reprezentacji. Będzie to trudne, jeśli wcześniej nie widziałeś tego rodzaju materiału.

Ryan Williams
źródło