I am reading Landsberg's "Tensors: Geometry and Applications". Here he mentions tensor formulation of Strassen's algorithm and shows that the rank of Strassen's matrix multiplication tensor is $7$ and $7$ is the lower bound for any such tensor and hence one needs $7$ multiplications for $2 \times 2$ matrix multiplication. My question is the following: is $7$ the absolute lower bound among all algorithms or just those that can be formulated via tensors?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What exactly do you mean by "any algorithm"? IMHO any procedure performing a sequence of arithmetic operations can be expressed by the tensor formalism, but beyond that one cannot say anything. $\endgroup$– Dima PasechnikCommented Apr 1, 2013 at 13:17
-
1$\begingroup$ @Dima Pasechnik not necessarily. For instance, you can easily compute the square of a real 2x2 matrix with only 5 multiplications, but this is an algorithm that exploits commutativity, and thus cannot be recast in bilinear "tensor language". $\endgroup$– Federico PoloniCommented Apr 1, 2013 at 20:55
-
$\begingroup$ @Federico Poloni Do you have the reference for this? $\endgroup$– TurboCommented Apr 1, 2013 at 22:30
-
2$\begingroup$ @unknown: I am not sure for which part you want a reference, but if it is that it works for 5 mults, just note that denoting the entries of the matrix a,b,c,d the entries of the square can be written, assuming commutativity, as a^2+bc, b(a+d), c(a+d), d^2+bc. So the first needs 2 mults, but the 4th only one in addition as bc is already known. $\endgroup$– user9072Commented Apr 1, 2013 at 23:24
-
$\begingroup$ That is the same algorithm that I had in mind. $\endgroup$– Federico PoloniCommented Apr 2, 2013 at 17:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
This $7$ is an absolute lower bound. The result is due to Hopcroft and Kerr "On minimizing the number of multiplications necessary for matrix multiplication." SIAM J. Appl. Math. (1971) and Winograd "On multiplication of $2\times 2$ matrices." Linear Algebra and Appl. (1971). [The former assume that entries of the matrices might not commute; while the latter gets the bound even assuming commutativity of the entries.]
A lot more recently Landsberg showed that not only the rank but even the border rank of multiplication of $2 \times 2$ matrices is $7$, meaning very roughly that also small perturbations cannot lead to a smaller rank and thus saving of a multiplciation (for "approximate" calculations), assuming bilinearity of the algorithm.
The paper establishing this is Landsberg "The border rank of the multiplication of $2\times 2$ matrices is seven", Journal Amer. Math Soc. 2006. The introduction also discusses your question.
See the link at the end for the respective volume of the journal, I think the article is free: http://www.ams.org/journals/jams/2006-19-02/home.html
-
4$\begingroup$ The rank and border rank bounds deal only with bilinear algorithms (which may be less efficient by a small factor - a bound of 2 is not hard to prove). In particular, Winograd proved something stronger than just that the rank is 7, since he does not restrict his attention to bilinear algorithms. When Landsberg says "The precise number of multiplications needed to execute matrix multiplication (or any given bilinear map) is called the rank of the bilinear map", he is implicitly assuming bilinearity of the algorithm. $\endgroup$ Commented Apr 1, 2013 at 13:50
-
$\begingroup$ @Henry Cohn: thank you for this clarification; I will slightly edit my answer to avoid suggesting something possibly misleading. $\endgroup$– user9072Commented Apr 1, 2013 at 14:07
$\begingroup$
$\endgroup$
2
Quid's reply already gives you a complete answer for the $2\times 2$ case; however, there is an additional consideration that adds to the picture of the optimal exponent of matrix multiplication.
One can prove that, for any $t$, if there exists a straight-line program that multiplies $n\times n$ matrices in $O(n^t)$ ops (without any bilinearity assumption or restriction on the operations made: divisions, additions, products of three more terms, everything is allowed), then there is a bilinear algorithm (i.e., one that can be "formulated with tensors") that achieves the same asymptotic complexity $O(n^t)$. So one does not lose generality by restricting to bilinear algorithms, when looking for the optimal exponent of matrix multiplication.
I had this same doubt myself a few years ago, and I found a proof of this statement in Borodin-Munro, The computational complexity of algebraic and numeric problems.
answered Apr 1, 2013 at 20:51
-
$\begingroup$ Interesting observtion. However I wonder is straightline restriction necessary? $\endgroup$– TurboCommented Apr 1, 2013 at 22:28
-
$\begingroup$ If you remove it, and work in finite precision arithmetic, then you can replace an arithmetic operation with a bazillion if's and assignments. But I guess that it can be removed, if one restricts to algorithms that do not "cheat" using real number representations. $\endgroup$ Commented Apr 2, 2013 at 17:40