Idée commune dans la multiplication de Karatsuba, Gauss et Strassen

Les identités utilisées dans les algorithmes de multiplication par

• Karatsuba (entiers)

• Gauss (nombres complexes)

• Strassen (matrices)

semblent très proches. Existe-t-il un cadre abstrait / généralisation commun?

Le cadre classique est celui des algorithmes bilinéaires et des décompositions de rang de tenseur; Fondamentalement, vous construisez le tenseur à 3 voies associé à la carte bilinéaire $f(A,B) = A \cdot B$ , sur la base des coefficients, puis recherchez une décomposition de celui-ci comme une somme de tenseurs de rang 1 (c.-à-d. ceux de la forme $T_{i,j,k} = u_i v_j w_k$ ). Vous trouverez cela expliqué plus en détail, par exemple, dans cet article de Bläser , ou dans le livre de Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory.

Pour autant que je comprends, la reformulation en termes de représentations de groupe que Suresh mentionne dans sa réponse est plus tardive, et je la trouve moins appropriée pour une première approche du sujet (mais, bien sûr, cela pourrait être un parti pris de ma part ).

Une réponse partielle à votre question est l'approche de la théorie des groupes d'abord développée par Cohn et Umans puis développée par Cohn, Kleinberg, Szegedy et Umans. Il peut "en quelque sorte" capturer Strassen et Coppersmith-Winograd pour la multiplication matricielle.