The identities used in multiplication algorithms by
seem very closely related. Is there a common abstract framework/generalization?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ Look up Schönhage's asymptotic sum inequality. $\endgroup$– Yuval FilmusMay 18, 2012 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, 2012 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$– sdcvvcMay 18, 2012 at 11:31
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
-
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$ Dec 27, 2018 at 10:09
$\begingroup$
$\endgroup$
1
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.
-
$\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$ Dec 27, 2018 at 10:07