In Prof. Tim Roughgarden's course on the design and analysis of algorithms on Coursera, a question regarding how can we derive this formula is posed. It is clear how to prove it, however what thinking methodology can you follow to reason such non-trivial results?
This is not a comment on how Strassen devised the method, but a more general comment on a the thinking methodology per you last second question:
"what thinking methodology..."
A lower bound on the complexity was known, since there are n^2 elements,
and changing any one of them would change the result, then at least n^2 operations were needed.
An upper bound of n^3 was known using the usual algorithm for matrix multiplication.
Since these are not equal, the actual complexity could be anywhere in
between (inclusive).
Now, try to prove, through proof by contradiction, that there cannot be an
algorithm which takes less than n^3 operations. This is not
possible, but it leaves you with candidates for how it might be done.
I have not done this with Strassen's but it is a useful technique.
This is in fact how hyperbolic geometry was shown to be every bit as
valid if the parallel postulate was removed from the postulates for
Euclidean geometry.
Strange looking diagrams of "lines" in hyperbolic geometry
which were non-intersecting because they were aymptotic,
which led to the frustrated (and erroneous) contradiction:
"But this is repugnant to the nature of a straight line".
Thanks for your answer. I am not sure if I got it. Will this reasoning make me believe there is a compromise between a quadratic and cubic complexities or the choice of his seven products? I would like to know how did he reason about these specific seven products.
If you take a look n by n matrices where is is even, and consider
using block multiplication of the n/2 by n/2 submatrices, then
you can try to prove that there is no way to get the product in fewer than
8 ( 2 cubed) submatrix multiplications. (You can have any number of
finite additions, since they contribute only to the n squared term, so asymptotically
they do not matter.)
Clearly there is some combination, and Strassen found it, so
you cannot prove that it is impossible to do so.
Proof by contradiction starts out with:
Suppose there is a way (e.g. with 7 multiplications and any number of additions)
then reason forward until you come to a contradiction.
You can't, so you must either give up, or find such a way, then using a recursive technique to multiply matrices, you can show that the asymptotic complexity
is n to the log-base-2 ( 7 ) which is less than n cubed.
Strassen may either have believed there was such a case, or he may
have been trying to proved n cubed was optimal by contradiction, either way,
he found such a combination.
The big idea is that such an algorithm may exist. The rest is discovery and
calculation.
Since a matrix multiplication involves O(n^2) entries, then intuitively and ideally we hope that it will run essentially wtih O(n^2) flops. However, devising an algorithm for matrix multiplication with approximate O(n^2) flops is nontrivial. Strassen's algorithm is just a typical effort to this end.
I would like to refer you to :Robinson, Sara, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38(9), November 2005, for details about this research.
My guess is Strassen got inspiration for his divide-and-conquer matrix multiplication from the Karatsuba(-Ofman) method for multiplication of large integers. See:
http://mathworld.wolfram.com/KaratsubaMultiplication.html
http://en.wikipedia.org/wiki/Karatsuba_algorithm
http://people.cs.uchicago.edu/~laci/HANDOUTS/karatsuba.pdf
Addendum: According to statements here
http://cstheory.stackexchange.com/questions/21564/why-did-kolmogorov-publish-karatsubas-algorithm
the result I cited above is only due to Karatsuba. Ofman apparently had an unrelated result in the same paper. I do not claim to know the provenance myself, but it is commonly referred to as "the Karatsuba method" despite the fact that the relevant publication had two authors.
I guess it's a matter of philosophy as to what is/are the essential ingredients for this method. But it's fair to state that without divide and conquer aspect, Strassen's method for multiplication would not be asymptotically faster than cubic. As to whether this approach was obvious in 1968 when Strassen did the work, I simply do not know. But I've seen no literature to suggest it was attempted before Strassen published his result.
As for th 7-for-8 multiplication of 2x2 matrices, again I have no definitive origination. My 1974 copy of the Aho, Hopcroft, Ullman text The Design and Analysis of Computer Algorithms does in fact credit this to Strassen.
I guess the final arbiter on what might have been the influences would be Strassen himself.
Please check this for a derivation of Strassen's algorithm.
http://jacobminz.blogspot.in/2015/05/derivation-of-strassens-algorithm-for.html
From the derivation, it is possible that many such 7 products would exist, and not just the ones we have seen in the textbook. However, Strassen's products beautifully exploits the symmetries in the computation, by making the calculation "uneven" for a given c[i][j]. That is, to start with we have similarly looking formula for every c[i][j], and there was no way to reduce the 8 multiplications if we didn't do anything about it. However by systematically perturbing the uniform formula, to a nonuniform one, we uncover a symmetric product, which reduces the 8 multiplications to 7, albeit increasing the cheaper operations of addition.
- Badges
- Science topic