Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Dima Pasechnik Apr 1 '13 at 13:17
1  
@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". –  Federico Poloni Apr 1 '13 at 20:55
    
@Federico Poloni Do you have the reference for this? –  Turbo Apr 1 '13 at 22:30
2  
@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. –  quid Apr 1 '13 at 23:24
    
That is the same algorithm that I had in mind. –  Federico Poloni Apr 2 '13 at 17:37

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
4  
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. –  Henry Cohn Apr 1 '13 at 13:50
    
@Henry Cohn: thank you for this clarification; I will slightly edit my answer to avoid suggesting something possibly misleading. –  quid Apr 1 '13 at 14:07

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.

share|improve this answer
    
Interesting observtion. However I wonder is straightline restriction necessary? –  Turbo Apr 1 '13 at 22:28
    
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. –  Federico Poloni Apr 2 '13 at 17:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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