User talk:Singleheart

Matrix multiplication

You wrote:

Stothers or Williams didn't propose a new algorithm. They gave a new analysis of the Coppersmith and Winograd's algorithm.

But this isn't so -- the algorithms that Stothers and Williams propose are actually faster than the one proposed by Coppersmith & Winograd. The algorithms are the same except for the A used. In particular, Stothers used the tensor square of and Williams the fourth tensor power of the A used in Coppersmith & Winograd's O(n^2.376) algorithm (which, in turn, is the tensor square of another A that I think was also first mentioned in the Coppersmith & Winograd paper).

True, their main contribution was a better method of analysis. But the algorithms are different: they did not merely give better bounds for the existing algorithm. And not all tensor powers lead to faster algorithms: Coppersmith & Winograd ask for the performance of the third tensor power of the original (slower/smaller) A and a later paper (sorry, don't remember the reference) showed it to be slower.

CRGreathouse (t | c) 17:54, 1 December 2011 (UTC)

That ("didn't propose a new algorithm") was my mistake. Actually the algorithms are not the same. But, Stothers and Williams's algorithms are still in the framework of CW's algorithm. "CW's algorithm is the third" is true, but inappropriate. --Singleheart (talk) 03:03, 2 December 2011 (UTC)

I agree that they're in the same framework, and it's not clear what's appropriate. I'll leave your version up (or whatever happens to be there now). But the wording should be checked to make sure credit is given where due. :) CRGreathouse (t | c) 05:51, 2 December 2011 (UTC)

Oh, and welcome to Wikipedia, by the way. CRGreathouse (t | c) 05:51, 2 December 2011 (UTC)

Thanks. I've modified the article a bit. --Singleheart (talk) 06:39, 2 December 2011 (UTC)