Wspólny pomysł w mnożeniu Karatsuba, Gaussa i Strassena

19

Tożsamości używane w algorytmach mnożenia przez

Karatsuba (liczby całkowite)
Gauss (liczby zespolone)
Strassen (matryce)

wydają się bardzo blisko spokrewnione. Czy istnieje wspólna abstrakcyjna struktura / generalizacja?

algorithms matrices

— sdcvvc
źródło

3

Sprawdź asymptotyczną nierówność sumy Schönhage'a.

— Yuval Filmus

O jakich tożsamościach mówisz? Czy mamy przeczytać wszystkie trzy artykuły, aby odpowiedzieć? Dodaj odpowiednie informacje do swojego pytania.

— Raphael

1

@Raphael: Tożsamości, które są podstawą algorytmów, wyrażając 4

— krotne

5

$f(A,B) = A \cdot B$ $T_{i,j,k} = u_i v_j w_k$ ). Znajdziesz to wyjaśnione bardziej szczegółowo, na przykład w tym artykule Bläser lub w książce Bürgissera, Clausena, Shokrollahi, Algebraic Complexity Theory.

O ile rozumiem, przeformułowanie w kategoriach reprezentacji grupowych, o których wspomina Suresh w swojej odpowiedzi, jest późniejsze i uważam, że mniej nadaje się do pierwszego podejścia do tematu (ale oczywiście może to być stronnicze z mojej strony ).

— Federico Poloni
źródło

1

To jest poprawna odpowiedź. Jednym aspektem, którego brakuje, jest tensorizacja / podział i podbijanie, który stoi zarówno za algorytmem Karatsuba, jak i szybkimi (kwadratowymi) algorytmami mnożenia macierzy.

— Yuval Filmus

8

Częściowa odpowiedź na twoje pytanie to teoretyczne podejście grupy opracowane przez Cohna i Umansa, a następnie rozwinięte przez Cohna, Kleinberga, Szegedy i Umansa. Może „niejako” uchwycić Strassen i Coppersmith-Winograd w celu pomnożenia macierzy.

— Suresh
źródło

To naprawdę nie ma sensu. Grupowe podejście teoretyczne jest tak naprawdę tylko jednym ze sposobów wymyślenia takich tożsamości.

— Yuval Filmus