Talk:Strassen algorithm

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science Low‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles Low This article has been rated as Low-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Computing: Software Low‑importance This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles Low This article has been rated as Low-importance on the project's importance scale. This article is supported by WikiProject Software (assessed as Low-importance). Mathematics Low‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Low This article has been rated as Low-priority on the project's priority scale.

An example of this actually being implemented would be a nice addition to the article. I searched the web and didn't find a single example of this algorithm actually being implemented. Sure you can talk about the algorithm all day, but it means nothing if no one can put it into code. —Preceding unsigned comment added by 69.239.153.215 (talk) 13:22, 2 January 2009 (UTC)[reply]

link to reference 1 is broken 75.142.209.115 (talk) 19:46, 29 October 2008 (UTC)[reply]
link to reference 2 is broken as well Nov 12, 2008

Thanks for your comments. I fixed the references. -- Jitse Niesen (talk) 13:34, 12 November 2008 (UTC)[reply]

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 are 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)[reply]

The larger importance of multiplications becomes apparent when one starts to use the algorithm recursively, since the additions and multiplications at all but the bottom levels are then matrix additions and multiplications. A matrix multiplication is near O(${\displaystyle n^{3}}$), whereas the matrix addition is O(${\displaystyle n^{2}}$). Hence the number of additions in a Strassen-type matrix multiplication algorithm only affects the constant factor, but the number of multiplications affect the exponent. See section 2.4 of Wilf, Herbert S. Algorithms and Complexity.81.231.33.217 (talk) 13:29, 30 June 2008 (UTC)[reply]

Yes, the reduction in complexity is a purely mathematical result independent of any computer implementation. I've fixed the article. 128.232.237.113 (talk) 22:41, 5 March 2009 (UTC)[reply]

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 ${\displaystyle \mathbb {K} }$? Pmdboi 18:05, 19 February 2006 (UTC)[reply]

Some texts use ${\displaystyle \mathbb {K} }$ 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)[reply]

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)[reply]

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)[reply]

Little bit necro but I think the formula is wrong indeed. Either ${\displaystyle \mathbf {M} _{6}}$ should be ${\displaystyle (-\mathbf {A} _{1,1}+\mathbf {A} _{2,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})}$ or ${\displaystyle \mathbf {M} _{6}}$ should be used as ${\displaystyle \mathbf {-M} _{6}}$ in the ${\displaystyle \mathbf {C} _{2,2}}$ formula. -- IcePhoenX (talk) 09:54, 19 June 2015 (UTC)[reply]

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)[reply]

Agreed. A crossover point certainly exists, but is hardware dependent. I'll put something fluffier in. Deco 05:18, 23 February 2007 (UTC)[reply]

Winograd's 7 multiplications and fewer additions than Strassen algorithm was published 1971 (Winograd, S. (1971). "On Multiplication of 2×2 Matrices". Linear Algebra and Its Applications. 4: 381–388.), not 1980. It has the same asymptotic complexity as Strassen's: ${\displaystyle O(n^{\log _{2}7})}$.

The "Ultra-fast matrix multiplication" reference in the article describes another matrix multiplication attributed to Winograd, which has asymptotic complexity O(${\displaystyle n^{3}}$). It is possible that this was published in 1980.

That time period also saw many other developments which are worth mentioning:

• The first Strassen-like algorithm — in the sense of a computational scheme for multiplication of matrices of a fixed size that uses clever tricks to reduce the number of element multiplications needed — to achieve better asymptotic complexity than Strassen's original algorithm (Pan, V. Ya. (1980). "New fast algorithms for matrix operations". SIAM Journal on Computing. 9 (2): 321–342. ISSN 0097-5397.). It's wasn't too practical though, as it still used 47216 multiplications to multiply two 48×48 matrices, thus only reducing the exponent by 0.02.
• The Strassen-Schönhage algorithm (which is not the same as the Schönhage-Strassen algorithm for integer multiplication), which reduced the exponent to below 2.5.Schönhage, A. (1981). "Partial and total matrix multiplication". SIAM Journal on Computing (3): 434–455. {{cite journal}}: Unknown parameter |volumne= ignored (help) (I don't recall the details, and haven't got de Groote, H. F. (1987). Lectures on the Complexity of Bilinear Problems. Lecture Notes in Computer Science. Vol. 245. Springer. ISBN 3-540-17205-X. at hand so I can check; possibly Strassen's contribution was to push the exponent below 2.5.)

81.231.33.217 (talk) 14:08, 30 June 2008 (UTC)[reply]

• It is asymptotically faster than the standard matrix multiplication algorithm

What does asymptotically faster mean? Thanks, --Abdull (talk) 10:55, 25 July 2008 (UTC)[reply]

"For large enough input", in this case "for large enough matrix sides". 81.231.34.61 (talk) 10:49, 11 September 2008 (UTC)[reply]

The section entitled "Numerical Analysis" should be "Performance Analysis". Numerical Analysis could include an analysis of any of: numerical stability, error accumulation, bit accuracy (vs. precision), or the correctness of the algorithm (though that may be a stretch). It does mention the first (numerical stability) but there is no actual analysis, just a mention and a general link. I also think that there is some problem with the performance analysis, but I will go into that separately. --RBarryYoung (talk) 13:20, 5 January 2010 (UTC)[reply]

Statements about relative speed are vague.

See Modern Computer Algebra (MCA) by Joachim von zur Gathen and Jurgen Gerhard for EXTENSIVE discussion of Strassen algorithm.

Put in citations to MCA and to relevant work it cites. Michael P. Barnett (talk) 16:54, 3 May 2011 (UTC)[reply]

This article may require cleanup to meet Wikipedia's quality standards. The specific problem is: the article contains vague statements and lacks references to work it mentions and to the considerable relevant work that it ignore. This should be ignores, and the template is poorly written. Doug (talk) 04:33, 16 April 2012 (UTC)[reply]

I was looking at the code and see that this version is a memory hog. Could it be more optimized if it were using location references instead of creating a new submatrix to perform each of the operations on? — Preceding unsigned comment added by 71.227.161.5 (talk) 09:14, 6 May 2012 (UTC)[reply]

${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.807})}$

2.807 is a blunder. Right 2.8074 or 2.81. Very simple Russion МетаСкептик12 (talk) 18:24, 1 July 2012 (UTC)[reply]

DeepMind has used its board-game playing AI AlphaZero to discover a faster way to multiply matrices, see https://www.technologyreview.com/2022/10/05/1060717/deepmind-uses-its-game-playing-ai-to-best-a-50-year-old-record-in-computer-science/ — MFH:Talk 16:58, 12 October 2022 (UTC)[reply]

The Winograd form section claims that the form has 15 additions or subtractions, but the algorithm shown has 22. I could combine identical operations by introducing new variables but this might be seen as original research. How should we proceed? Cheers, cmɢʟee⎆τaʟκ 12:31, 6 December 2023 (UTC)[reply]

I would guess someone made a mistake writing down the algorithm here, as other wiki articles also cite 12 additions. It would be nice if someone who understood what's going on in the paper would fix it. TheBooker66, but call me Ethan (talk) 14:51, 28 November 2024 (UTC)[reply]