19
$\begingroup$

The identities used in multiplication algorithms by

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

$\endgroup$
  • 3
    $\begingroup$ Look up Schönhage's asymptotic sum inequality. $\endgroup$ – Yuval Filmus May 18 '12 at 5:12
  • $\begingroup$ 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. $\endgroup$ – Raphael May 18 '12 at 7:42
  • 1
    $\begingroup$ @Raphael: The identities which are foundations for the algorithms, expressing 4 number multiplications with 3 multiplications, and 8 matrix multiplications with 7. $\endgroup$ – sdcvvc May 18 '12 at 11:31
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 27 '18 at 10:09
8
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.