Talk:Coppersmith–Winograd algorithm

From Wikipedia, the free encyclopedia

This should probably be tagged as a stub since it doesn't contain the actual algorithm nor much of a discussion past the big O complexity. I'd do it, but I don't know the algorithm. Lavid 19:46, 25 February 2007 (UTC) lavid

Actually, I do not think anyone has ever written down the full algorithm. The paper only proves that such an algorithm exists. I do not think we can provide an explanation of the technique here without writing an essay as complex as Coppersmith and Winograd's paper. Publishing a short introduction here and a link to the paper is probably the best we can do. 192.167.206.227 14:55, 15 May 2007 (UTC)

Is this the same as the Winograd algorithm for matrix multiplication? I'm reading about Winograd algorithm in one book right now, and it has quite concise explanation of how the algorithm works. I could give this explanation here, but for some reason I'm not quite sure if it is the same thing. The book is available on Internet (here's the link), however it might not be of much use to you since it's in Serbian :P -- Obradović Goran (talk 00:19, 19 July 2007 (UTC)
According to Strassen algorithm#History, there is an algorithm due to Winograd in 1980 and another one published in 1990 by Coppersmith and Winograd. Could it be that your book describes the 1980 algorithm? That would also be worthwhile to describe. Winograd's 1980 algorithm is described at http://www.f.kth.se/~f95-eeh/exjobb/background.html . Alternatively, if you give me the page in your book where I should look at, I could have a look - formulas are the same whatever language the book is written. -- Jitse Niesen (talk) 13:14, 23 July 2007 (UTC)
Yes, it appears that it is the 1980 algorithm. It is said in Serbian text (which is the main reason why I had my doubts that it is this algorithm), that Strassen algorithm is more efficient than Winograd algorithm. The algorithm is described on the page 212 of the book (220 in .pdf) - just search for winograd. I will translate here the description, since it is very short:

Because of simplicity, let us assume that n is even number. Let's introduce the notation

P_i = \sum_{k=1}^{n/2} p_{i, 2k-1} p_{i, 2k}; i = 1, 2, ... , n,

Q_j = \sum_{k=1}^{n/2} q_{2k-1, j}q_{2k, j}; j = 1, 2, ... , n.

By regrouping, we get

r_{ij} = \sum_{k=1}^{n/2}(p_{i, 2k-1} + q_{2k, j})(p_{i, 2k} + q_{2k-1, j}) - P_i - Q_j

Numbers Pi and Qj are calculated only once fore each row P, and column Q, which takes only n^2 multiplications. Total number of multiplications is therefore decreased to n3 / 2 + n2. Number of additions is increased for approximately n^3/2. The algorithm is therefore better than direct one in case when addition is faster than multiplication (which is usually the case).

Comment. Winograd algorithm shows that changing of the order of calculation may decrease the number of calculations, even in expressions like matrix multiplication, which are simple in form. Next algorithm [Strassen] exploits the same idea much more efficiently.

-- Obradović Goran (talk 20:08, 17 May 2008 (UTC)