Strassen's Algorithm proof

Question

I have been reading about the Strassen Algorithm for matrix multiplication.

As mentioned in Introduction to Algorithms by Cormen , the algorithm is not intuitive. However I am curious to know if there exists any rigorous mathematical proof of the algorithm and what actually went into the design of the algorithm.

I tried searching on Google and stackoverflow, but all links are only on comparing Strassen's approach to standard matrix multiplication approach or they elaborate on the procedure presented by the algorithm.

Answer 1

You should go to the source material. In this case, the original paper by Strassen:

Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969

http://link.springer.com/article/10.1007%2FBF02165411?LI=true

Even though I haven't read it myself, I would assume that there is a rigorous discussion and proof of the complexity of the algorithm.

It looks like Professor Strassen is still active (http://en.wikipedia.org/wiki/Volker_Strassen) and has a home page (http://www.math.uni-konstanz.de/~strassen/). If, after learning as much as you can about the algorithm, you are still interested in learning more, I don't think a carefully worded email to the professor would be out of the question.

Unfortunately, there does not seem to be a free version of the paper available online despite the fact that the work was completed at a public university (UC Berkeley) using federal funds (NSF grant), but that is a completely separate issue we shouldn't discuss here.

If you are a student, you will likely have access via your school, or at least your school could get you a copy without cost to you. Good luck.