37
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Fascinating. Can any expert quickly comment on why that exponent and what is conjectured optimal? $\endgroup$ Sep 15, 2010 at 19:57
  • 11
    $\begingroup$ 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$. $\endgroup$ Sep 15, 2010 at 22:16
  • $\begingroup$ Wiki has surprisingly good pointers for intro to the field en.wikipedia.org/wiki/Matrix_multiplication_algorithm $\endgroup$
    – Rohin
    Nov 25, 2020 at 22:33

10 Answers 10

23
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ As for the exercises in The Art of Computer Programming, they are exercises 66,67 and a few before that, chapter 4.6.4, for me, it is page 523. $\endgroup$ Dec 5, 2020 at 17:38
22
$\begingroup$

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.

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

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – ilyaraz
    Aug 2, 2010 at 0:32
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ I know Karatsuba and Strassen algorithms. And they doesn't seem to help in understanding more advanced techniques. :) $\endgroup$
    – ilyaraz
    Aug 2, 2010 at 0:30
3
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ It seems Ryan Williams gave this link in his answer of 2 August 2010. $\endgroup$ Mar 4, 2011 at 4:47
  • $\begingroup$ Yes, you are right. I did not saw it $\endgroup$ Mar 5, 2011 at 17:15
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Where is Josh Alman and Virginia Vassilevska Williams code? I wonder why dont these researchers publish their code. $\endgroup$ Jun 7, 2022 at 14:27
2
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ This book does not seem to be readable at all. :( $\endgroup$
    – ilyaraz
    Aug 3, 2010 at 0:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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