Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Fascinating. Can any expert quickly comment on why that exponent and what is conjectured optimal? –  Piero D'Ancona Sep 15 '10 at 19:57
3  
I'm not sure it's possible to quickly comment on why this exponent arises... the exponent is really $2.375\cdots$, and it′s what you get when you find the minimum solution to some funky system of equations. Experts differ on what the optimal exponent should be. Strassen has conjectured that the bound should be $\Theta(n^{2+\delta})$ for some $\delta > 0$. Others believe that $n^{2+\delta}$ may be possible for every $\delta >0$. –  Ryan Williams Sep 15 '10 at 22:16

8 Answers 8

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.

share|improve this answer
    
I'll try to read them. But firstly, I need to improve my knowledge about representations. –  ilyaraz Aug 2 '10 at 0:43
3  
Anyway: 1) matrix multiplication $\mathbb F^{m\times n}\times \mathbb F^{n\times p}\to \mathbb F^{m\times p}$ is a bilinear map - if you choose the canonical bases for the three spaces, you get the structural tensor. 2) The tensor rank is the minimum number $r$ of "triads" $a \otimes b \otimes c$ so that you can write your tensor $T$ as $$T=\sum_{i=1}^r a_i \otimes b_i \otimes c_i$$ –  Federico Poloni Aug 2 '10 at 23:05
1  
No. These papers is definitely what I was looking for. They are actually readable. :) –  ilyaraz Aug 3 '10 at 4:33
3  
If you haven't done so already, you might start by reading up on the algorithms for fast integer multiplication and fast Fourier transform. You can think of the matrix multiplication problem as a much harder analogue of these problems, where analogous solutions would rely on complicated group-theoretic constructions. en.wikipedia.org/wiki/… en.wikipedia.org/wiki/Fast_Fourier_transform –  Gene S. Kopp Aug 13 '10 at 17:32
1  
I don't understand how can one try to learn fast matrix multiplication without knowledge of FFT. :) –  ilyaraz Aug 13 '10 at 17:39

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)

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

share|improve this answer

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

share|improve this answer
1  
This survey is a great read, though it is without many technical details. It seems that this field is based on representation theory and rather advanced group theory. –  ilyaraz Aug 2 '10 at 0:32

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

share|improve this answer
    
I know Karatsuba and Strassen algorithms. And they doesn't seem to help in understanding more advanced techniques. :) –  ilyaraz Aug 2 '10 at 0:30

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

share|improve this answer
1  
This book does not seem to be readable at all. :( –  ilyaraz Aug 3 '10 at 0:24

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

share|improve this answer

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

share|improve this answer
    
It seems Ryan Williams gave this link in his answer of 2 August 2010. –  Gerry Myerson Mar 4 '11 at 4:47
    
Yes, you are right. I did not saw it –  Klim Efremenko Mar 5 '11 at 17:15

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.