# Common idea in Karatsuba, Gauss and Strassen multiplication

The identities used in multiplication algorithms by

seem very closely related. Is there a common abstract framework/generalization?

• Look up Schönhage's asymptotic sum inequality. – Yuval Filmus May 18 '12 at 5:12
• Which identities are you talking about? Are we supposed to read all three articles in order to answer? Please add the relevant information to your question. – Raphael May 18 '12 at 7:42
• @Raphael: The identities which are foundations for the algorithms, expressing 4 number multiplications with 3 multiplications, and 8 matrix multiplications with 7. – sdcvvc May 18 '12 at 11:31

The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $$f(A,B) = A \cdot B$$, in the basis of the coefficients, then look for a decomposition of it as a sum of rank-one tensors (i.e., those of the form $$T_{i,j,k} = u_i v_j w_k$$). You'll find this explained in more detail, for instance, in this article by Bläser, or in the book by Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory.

As far as I understand, the reformulation in terms of group respresentations that Suresh mentions in his answer is a later one, and I find it less suitable for a first approach to the subject (but, of course, that might be bias on my part).

• This is the correct answer. One aspect which is missing is the tensorization / divide-and-conquer which is behind both Karatsuba's algorithm and fast (square) matrix multiplication algorithms. – Yuval Filmus Dec 27 '18 at 10:09

A partial answer to your question is the group-theoretic approach first developed by Cohn and Umans and further developed by Cohn, Kleinberg, Szegedy and Umans. It can "sort of" capture Strassen and Coppersmith-Winograd for matrix multiplication.

• This really misses the point. The group theoretic approach is really just one way of coming up with such identities in the first place. – Yuval Filmus Dec 27 '18 at 10:07