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

Strassen Algoritm is a well-known matrix multiplication divide and conquer algorithm. The trick of the algorithm is reducing the number of multiplications to 7 instead of 8. I was wondering, can we reduce any further? Can we only do 6 multiplications?

Also, what happens if we divide the NxN arrays into 9 arrays each of (N/3)x(N/3) instead of 4 arrays of (N/2)x(N/2). Can we then do less multiplications?

share|improve this question
1  
In view of your comment on Igor Rivin's answer: first reading your question, it seemed to me (and I guess to him) that you are interested in fast matrix multiplication in a sort of general way. In particular, the second paragraph caused this impression. –  quid Mar 7 '11 at 21:35

5 Answers 5

up vote 13 down vote accepted

You may be interested to know that there's a way to multiply $3\times3$ matrices using only 23 multiplications (where the naive method uses $27$). See Julian D. Laderman, A noncommutative algorithm for multiplying $3\times3$ matrices using $23$ muliplications, Bull. Amer. Math. Soc. 82 (1976) 126–128, MR0395320 (52 #16117).

As for doing $2\times2$ with fewer than $7$ multiplications, this was proved impossible just a few years ago. See J M Landsberg, The border rank of the multiplication of $2\times2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), 447–459, MR2188132 (2006j:68034).

EDIT: As Mariano points out, Landsberg acknowledged a gap in the proof. But don't panic. The review, and my preceding paragraph, were based on the electronic version of Landsberg's paper. The print version (which is freely available on the AMS website) is different. It says, "Hopcroft and Kerr [12] and Winograd [22] proved independently that there is no algorithm for multiplying $2\times2$ matrices using only six multiplications."

Those references are

J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30–36, MR0274293 (43:58).

S.Winograd, On multiplication of $2\times2$ matrices, Linear Algebra and Appl. 4 (1971), 381–388, MR0297115 (45:6173).

share|improve this answer
    
There is a gap in that proof, according to the review; the latter mentions an erratum, but I cannot find it using MathSciNet. –  Mariano Suárez-Alvarez Mar 8 '11 at 0:01
1  
Wait... log_3(23) > log_2(7), so what is the point?... –  Michal R. Przybylek Mar 8 '11 at 1:04
2  
Michal, I was just trying to answer the question about dividing things in threes instead of twos, I didn't claim it was any better. But as far as I know (and I hope someone will catch me up, if my information is out of date), it has not been proved that $23$ is best possible for $3\times3$ matrices, all that's known is that it's at least $19$. –  Gerry Myerson Mar 8 '11 at 2:09
    
What Landsberg claims is stronger than what Hopcroft-Kerr and Winograd show. Landsberg claims that the border rank of $2 \times 2$ matrix multiplication is 7; this is stronger than proving that the rank of matrix multiplication is 7. Nevertheless, it looks like Landsberg patched his proof at arxiv.org/abs/math/0407224 –  Ryan Williams Mar 12 '11 at 2:31
1  
@unknown, try Marcus Blaser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003) 43-60, MR 2003k:68040. –  Gerry Myerson Nov 22 '11 at 5:36

Everything you ever wanted to know can be gleaned from:

http://en.wikipedia.org/wiki/Matrix_multiplication

share|improve this answer
    
I don't see where my questions are answered in the link you gave. It's justs repeats that "is based on a clever way of multiplying two 2 × 2 matrices which requires only 7 multiplications (instead of the usual 8), " –  Johny Mar 7 '11 at 20:57
    
There are references to the relevant papers in the wikipedia article. Since the methods are completely elementary, just read the papers. –  Igor Rivin Mar 8 '11 at 4:36

Of possible relevance to your question (though it might go into more geometric considerations than you care to read):

Generalizations of Strassen's equations for secant varieties of Segre varieties (J. Landsberg and L. Manivel, Comm. Algebra 2008)

share|improve this answer

I am not an expert in this field, but can hardly recall that:
- Strassen algorithm is optimal for divisions on 4 submatrices
- there are algorithms using a much larger number of submatrices and behaving slightly better.
If you are really interested in these results I can search for references, but be aware that the algorithms are of a very little practical use --- they just have big constant factors (and it is not the usual case that we are given a large dense matrix), and are not that robust (in the sense of numerical stability).

share|improve this answer
2  
Actually, Strassen's algorithm IS of practical use (the matrices have to be of the order of 200x200, although the precise numbers change with the hardware you use). There has been a lot of work done on numerical stability, and at least for Strassen this is well understood. –  Igor Rivin Mar 7 '11 at 21:45
    
@Igor: I assume Michal refers to the practicality of the other algorithms rather than that of the Strassen algorithm. –  Charles Mar 8 '11 at 1:30
    
@Charles: you might be right, I could not tell. In any case, I have recently been dealing with 10000x10000 matrices -- a size almost unimaginable 15 years ago, which means that methods which were once of academic interest only are (at least in principle) becoming practical. –  Igor Rivin Mar 8 '11 at 4:39

Best solution is in page 481, lines -1,-2, -3 and -4 of The art of Computer Programming, Volume two, Second Edition of Donald E. Knuth.

Also interesting to take a look to page 482.

He also references the original paper of Strassen as Numer. Math. 13 (1969), 354-356 in lines -5,-6,-7,-8 of the same page (481).

share|improve this answer

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.