Talk:Strassen algorithm
From Wikipedia, the free encyclopedia
While a lot of older textbooks will say that "additions don't matter, but multiplications do". That is usually not relevant anymore. Multiplying numbers is slower if you are working with multi-word representations of numbers (sometimes called 'big numbers'), but if you just multiplying "float"s or "double"s then multiplications and additions take the same amount of time on most processors (as far as i know) today. I'm going to change the article to say, "if we only consider multiplications" without the statement bout multiplications being inherently slower.... :)
- Yes, it depends on the sizes of the numbers being multiplied. Perhaps a clarification of this point should be added to the article? I'm not familiar with the size of the matrix components used in most matrix algorithms so I will defer this point to the experts. - Gauge 03:19, 21 Jan 2005 (UTC)
- This is mathematical thing, not a technical article. It states theoretical bounds.--213.141.159.52 14:30, 7 March 2006 (UTC)
I am unfamiliar with the use of blackboard bold to denote an arbitrary field, as I understand it to mean one of the canonical sets of numbers (e.g., the complex numbers, the integers, etc.). Shouldn't the article use K or K instead of 
? Pmdboi 18:05, 19 February 2006 (UTC)
- Some texts use or K to emphasize the point that K is a field but I think most text use a simple K instead. I changed the article accordingly. And I changed K into the more common F. MathMartin 19:09, 19 February 2006 (UTC)
Looking at Mathworld, I see a different formula for M1: http://mathworld.wolfram.com/StrassenFormulas.html Doing a simple case by hand, the wikipedia ones seem wrong. 141.218.136.204 20:07, 22 February 2007 (UTC)
- I"m sorry, but I don't see where the formula at MathWorld differs from the formula here. Could you please be more specific? -- Jitse Niesen (talk) 00:49, 23 February 2007 (UTC)
[edit] Cross-over point
I reverted the edit of 31 January 2007, which added this fragment:
- A popular misconception is that Strassen's algorithm outperforms the classic multiplication approach only for large matrix sizes. This is not true for modern architectures due to Strassen algorithm's superior cache behavior. For example, on a 2GHz Core Duo processor, Strassen's algorithm is three times faster at multiplying 128x128 matrices. It's time is pretty much the same as that block-multiplication for 256x256 and 512x512 matrices. For 1024x1024 and larger matrices (when the entire problem set no longer fits into processor's L2 cache), Strassen's algorithm is 3 times faster than block-multiplication and 12 times as fast as the classical three nested-loop implementation.
It might be true, but it does need a reference, especially since these kind of measurements are typically very dependent on details and it is contradicted by other references like Golub and Van Loan's Matrix Computations. -- Jitse Niesen (talk) 03:40, 23 February 2007 (UTC)
- Agreed. A crossover point certainly exists, but is hardware dependent. I'll put something fluffier in. Deco 05:18, 23 February 2007 (UTC)
