11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – user9072
    Commented Mar 7, 2011 at 21:35

5 Answers 5

Reset to default
17
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ There is a gap in that proof, according to the review; the latter mentions an erratum, but I cannot find it using MathSciNet. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Mar 8, 2011 at 0:01
  • 1
    $\begingroup$ Wait... log_3(23) > log_2(7), so what is the point?... $\endgroup$
    – Michal R. Przybylek
    Commented Mar 8, 2011 at 1:04
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Gerry Myerson
    Commented Mar 8, 2011 at 2:09
  • 2
    $\begingroup$ 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 $\endgroup$
    – Ryan Williams
    Commented Mar 12, 2011 at 2:31
  • 2
    $\begingroup$ @unknown, try Marcus Blaser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003) 43-60, MR 2003k:68040. $\endgroup$
    – Gerry Myerson
    Commented Nov 22, 2011 at 5:36
3
$\begingroup$

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)

Improve this answer
$\endgroup$
2
$\begingroup$

Everything you ever wanted to know can be gleaned from:

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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), " $\endgroup$
    – Johny
    Commented Mar 7, 2011 at 20:57
  • $\begingroup$ There are references to the relevant papers in the wikipedia article. Since the methods are completely elementary, just read the papers. $\endgroup$
    – Igor Rivin
    Commented Mar 8, 2011 at 4:36
0
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Igor Rivin
    Commented Mar 7, 2011 at 21:45
  • $\begingroup$ @Igor: I assume Michal refers to the practicality of the other algorithms rather than that of the Strassen algorithm. $\endgroup$
    – Charles
    Commented Mar 8, 2011 at 1:30
  • $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Commented Mar 8, 2011 at 4:39
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .