# 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. 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. 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.