MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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

-
Fascinating. Can any expert quickly comment on why that exponent and what is conjectured optimal? – Piero D'Ancona Sep 15 2010 at 19:57
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 2010 at 22:16

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

-

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

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

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

-

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

-
This book does not seem to be readable at all. :( – ilyaraz Aug 3 2010 at 0:24

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

-

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.

-
I'll try to read them. But firstly, I need to improve my knowledge about representations. – ilyaraz Aug 2 2010 at 0:43
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 2010 at 23:05
No. These papers is definitely what I was looking for. They are actually readable. :) – ilyaraz Aug 3 2010 at 4:33
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 2010 at 17:32
I don't understand how can one try to learn fast matrix multiplication without knowledge of FFT. :) – ilyaraz Aug 13 2010 at 17:39

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.