Gemeinsame Idee in Karatsuba, Gauss und Strassen Multiplikation

Die in Multiplikationsalgorithmen von verwendeten Identitäten

• Karatsuba (ganze Zahlen)

• Gauß (komplexe Zahlen)

• Strassen (Matrizen)

scheinen sehr eng miteinander verwandt zu sein. Gibt es einen gemeinsamen abstrakten Rahmen / eine gemeinsame Verallgemeinerung?

Das klassische Gerüst ist das der bilinearen Algorithmen und der Tensorrangzerlegung. Grundsätzlich man den 3-Wege - Tensor assoziiert mit der bilinearen Abbildung Konstrukt $f(A,B) = A \cdot B$ , in der Basis der Koeffizienten, dann für eine Zerlegung es als eine Summe von Rang-Eins - Tensoren (dh solche der Form $T_{i,j,k} = u_i v_j w_k$ ). Dies wird zum Beispiel in diesem Artikel von Bläser oder im Buch von Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory näher erläutert.

Soweit ich weiß, ist die Neuformulierung in Bezug auf Gruppenrepräsentationen, die Suresh in seiner Antwort erwähnt, eine spätere, und ich finde sie weniger geeignet für eine erste Herangehensweise an das Thema (aber das könnte natürlich voreingenommen sein von meiner Seite) ).

Eine teilweise Antwort auf Ihre Frage ist der gruppentheoretische Ansatz, der zuerst von Cohn und Umans entwickelt und dann von Cohn, Kleinberg, Szegedy und Umans weiterentwickelt wurde. Es kann Strassen und Coppersmith-Winograd für die Matrixmultiplikation "einfangen".