Q:
How did Strassen come up with his famous Strassen algorithm for matrix multiplication?
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?
How did Strassen come up with his famous Strassen algorithm for matrix multiplication? - ResearchGate. Available from: https://www.researchgate.net/post/How_did_Strassen_come_up_with_his_famous_Strassen_algorithm_for_matrix_multiplication [accessed Jan 15, 2017].
A:
The answer to the question is in the article of Robinson and Sara (SIAM News 38(9), 2005) suggested by Ke Zang. The idea can be seen as an extension of the Gauss complex multiplication algorithm to matrices. Gauss algorithm multiplies two complex numbers using 3 real multiplications instead of 4. Probably Strassen took the idea from there to arrange the elements of the matrices in order to eliminate one multiplication, as Gauss did for the elements of the two complex numbers.
How did Strassen come up with his famous Strassen algorithm for matrix multiplication? - ResearchGate. Available from: https://www.researchgate.net/post/How_did_Strassen_come_up_with_his_famous_Strassen_algorithm_for_matrix_multiplication [accessed Jan 15, 2017].
'via Blog this'
No comments:
Post a Comment