Fast Matrix Multiplication - MathOverflow

Fast Matrix Multiplication

2010-08-02T00:01:33Z

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.

Answer by András Salamon for Fast Matrix Multiplication

2010-08-02T00:21:11Z

Sara Robinson's survey Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38 (9), 2005, might be suitable.

Answer by Gerhard Paseman for Fast Matrix Multiplication

2010-08-02T00:26:30Z

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

Answer by Ryan O'Donnell for Fast Matrix Multiplication

2010-08-02T00:38:54Z

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.

Answer by Ryan Williams for Fast Matrix Multiplication

2010-08-02T02:48:46Z

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

Answer by Federico Poloni for Fast Matrix Multiplication

2010-08-02T23:00:04Z

There's a chapter on fast matrix multiplication on: Algebraic complexity theory - Peter Bürgisser, Michael Clausen, Mohammad Amin Shokrollahi.

Answer by Denis Serre for Fast Matrix Multiplication

2010-09-15T19:45:52Z

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

Answer by Klim Efremenko for Fast Matrix Multiplication

2011-03-03T23:12:56Z

http://www-cc.cs.uni-saarland.de/teaching/SS09/ComplexityofBilinearProblems/script.pdf It has some typos but except this it is really good.

Answer by Jon Yard for Fast Matrix Multiplication

2011-03-04T05:25:49Z

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