Talk:Coppersmith–Winograd algorithm: Difference between revisions

Revision as of 14:33, 23 September 2015

Latest revision as of 15:28, 24 December 2024

(13 intermediate revisions by 9 users not shown)

Line 1:

{{WikiProject banner shell|

{{maths rating

{{WikiProject Mathematics}}

|field = applied

|importance = low

|class = stub

|historical =

}}

{{annual readership|scale=log}}

{{Old merge full

| otherpage = Matrix multiplication algorithm

| date = April 30, 2021

| result = merge

| talk = Talk:Matrix multiplication algorithm#Merger proposal

| URL = https://en.wikipedia.org/wiki/Talk:Matrix_multiplication_algorithm#Merger_proposal}}

{{merged-to|Matrix multiplication algorithm|May 20, 2021}}

==algorithm==

Line 13 ⟶ 17:

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. [[User:192.167.206.227|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 ([http://www.matf.bg.ac.yu/~ezivkovm/nastava/algoritmi.pdf here's] the link), however it might not be of much use to you since it's in Serbian :P -- [[User:Obradovic Goran|Obradovi&#263; Goran ]] [[User talk:Obradovic Goran|(<fontspan colorstyle="color:red;">t</fontspan><fontspan colorstyle="color:blue;">a^l</fontspan><fontspan colorstyle="color:gray;">k</fontspan>]] 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. -- [[User:Jitse Niesen|Jitse Niesen]] ([[User talk:Jitse Niesen|talk]]) 13:14, 23 July 2007 (UTC)

Line 33 ⟶ 37:

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.

-- [[User:Obradovic Goran|Obradovi&#263; Goran ]] [[User talk:Obradovic Goran|(<fontspan colorstyle="color:red;">t</fontspan><fontspan colorstyle="color:blue;">a^l</fontspan><fontspan colorstyle="color:gray;">k</fontspan>]] 20:08, 17 May 2008 (UTC)

The article currently suggests that the algorithm does exist explicitly but doesn't give it with no explanation as to why. Having read the 1990 paper, it looks like this is because the algorithm is not explicitly constructed, only its existence is given. Can this be made clearer in the article? The suggestion that the algorithm isn't used in practice because it is slow for plausibly sized matrices is also questionable, is it not the case that the algorithm isn't used in practice because it hasn't been explicitly constructed [and possibly also too slow]? --[[Special:Contributions/131.111.213.41|131.111.213.41]] ([[User talk:131.111.213.41|talk]]) 03:28, 12 June 2009 (UTC)

Line 61 ⟶ 65:

:That is exactly what it says currently. --[[User:Mellum|mellum]] ([[User talk:Mellum|talk]]) 12:06, 16 November 2010 (UTC)

The point about needing to read all elements of both matrices gives us a lower *bound* on the minimum possible exponent, but it doesn't tell us that the *optimal* exponent is 2. In principle, it might be that it is mathematically impossible to do better than an exponent of, say, 2.1. I believe the conjecture is that there is no such problem, i.e. that, for each positive epsilon, there exists an algorithm whose exponent is not more than 2 + epsilon.

[[User:Jumpers for goalposts, enduring image|Jumpers for goalposts, enduring image]] ([[User talk:Jumpers for goalposts, enduring image|talk]]) 15:14, 22 May 2019 (UTC)

== 'Big News' update ==

Line 81 ⟶ 88:

However there is no citation or information explaining what said algorithm is. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/143.167.10.35|143.167.10.35]] ([[User talk:143.167.10.35|talk]]) 14:32, 23 September 2015 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== Pop Culture reference ==

This algorithm was mentioned obliquely (by the exponents of the runtime) in [https://www.smbc-comics.com/comic/mathematicians a recent SMBC comic]. Not sure if that's worth a subsection or not on the article. [[Special:Contributions/2620:0:1013:11:514D:10E:D51B:9F5A|2620:0:1013:11:514D:10E:D51B:9F5A]] ([[User talk:2620:0:1013:11:514D:10E:D51B:9F5A|talk]]) 16:27, 14 October 2019 (UTC)

That's how I got here... Last time I checked they (habitual wikipedia colaborators) were frowning upon "pop culture references", but haven't read recent discussions about it. --[[User:AstroNomer|AstroNomer]] ([[User talk:AstroNomer|talk]]) 18:22, 15 October 2019 (UTC)