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

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?

$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 ).

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.