Fast matrix multiplication Suppose we have two $n$ by $n$ matrices over particular ring. We want to multiply them as fast as possible. According to wikipedia there is an algorithm of Coppersmith and Winograd that can do it in $O(n^{2.376})$ time. I have tried to look at the original paper and it scares me. It seems that it is impossible to understand current state of the art.
So, the question is the following. Is there any 'gentle' introduction or survey for beginners in this particular field? I took only introductory course in algebra, so it would be nice to know what parts of algebra do these techniques rely on.
 A: An other reference, in French:
J. Abdeljaoued, H. Lombardi. Méthodes Matricielles. Introduction à la Complexité Algébrique. SMAI series ``Mathématiques et Applications''. Springer-Verlag (2003).
A: "Geometry and the complexity of matrix multiplication", by J. Landsberg from the AMS bulletin is a very nice article.  It describes an approach to this problem based on algebraic geometry, that of bounding the "border rank" of the sequence of bilinear maps defining matrix multiplication.  I don't think it reproduces the state of the art yet (but I'm not an expert so maybe), but it is a well-defined mathematical program that should in principle be able to uncover the optimal exponent.  I think at least the basics of the approach should be pretty understandable with a minimum of background, but the whole theory does go pretty deep and technical.  I believe this is, however, the nature of the beast - it is a shockingly deep question.
A: Instead of going for state-of-the art immediately, you might read a little bit on the history of the problem.  Karatsuba multiplication and the Strassen algorithm should give the core idea.  If you look at the Coppersmith-Winograd algorithm closely, you might find an implementation that will make it practical for small n, or a series of examples that will show why it won't be practical.
Gerhard "Ask Me About System Design" Paseman, 2010.08.01
A: http://www-cc.cs.uni-saarland.de/teaching/SS09/ComplexityofBilinearProblems/script.pdf
It has some typos but except this it is really good.
A: Francois LeGall has a great talk on this subject, although I don't think there is a matlab/C++ implementation. See  Powers of Tensors and Fast Matrix Multiplication
A: A recent article by Kevin Hartnett in Quanta magazine (Matrix Multiplication Inches Closer to Mythic Goal) is targeted at (math-inclined) laypeople and discusses the recent result of Josh Alman and Virginia Vassilevska Williams (A Refined Laser Method and Faster Matrix Multiplication) where they obtain the bound 2.37286.
A: Here are some resources I found useful while learning about this stuff.


*

*Victor Pan. How to Multiply Matrices Faster. Springer LNCS, 1984. A paperback edition was available on Amazon at some point, but no longer it seems. This monograph and Pan's 1980 journal paper (which improves on Strassen) are very readable:



Victor Y. Pan: New Fast Algorithms for Matrix Operations. SIAM J. Comput. 9(2): 321-342 (1980)



*

*Knuth, The Art of Computer Programming Vol 2 contains a series of exercises that lead you through an $o(n^{2.5})$ matrix multiplication algorithm. Unfortunately I don't have a copy in front of me, so I can't tell you the specific exercises.

*A nice exposition by Andrew Stothers: http://www.maths.ed.ac.uk/~s0237198/report1styr.pdf

*EDIT: There are some other lecture notes out there that I can't seem to dig up at the moment. Here they are: http://www-cc.cs.uni-saarland.de/teaching/SS09/ComplexityofBilinearProblems/script.pdf
If you search for "strassen laser method" you will find more nice hits. In principle, "schoenhage tau theorem" should also yield results, but it doesn't seem to. (These are the two prior results that Coppersmith-Winograd build on.)
A: You may also look at the alternative approach to Coppersmith-Winograd proposed by Cohn-Umans and Cohn-Kleinberg-Szegedy-Umans.  Their papers are very readable, and the latter gets close to the Coppersmith-Winograd exponent 2.376.  It is said that the methods in their paper can also achieve 2.376, but I don't think this is published.
A: There's a chapter on fast matrix multiplication on:
Algebraic complexity theory -  Peter Bürgisser, Michael Clausen, Mohammad Amin Shokrollahi.
A: Sara Robinson's survey Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38 (9), 2005, might be suitable.
