tag:blogger.com,1999:blog-3722233.post8978327258415406646..comments2024-05-26T22:10:45.398-05:00Comments on Computational Complexity: Will Strassen's Matrix Mult Alg ever be practical? Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-87661338406530810562023-02-21T08:18:28.952-06:002023-02-21T08:18:28.952-06:00For the definitive recent paper on the practical i...For the definitive recent paper on the practical implementation of Strassen's algorithm, see https://scholar.google.com/citations?view_op=view_citation&hl=en&user=62GM5XcAAAAJ&cstart=20&pagesize=80&citation_for_view=62GM5XcAAAAJ:dYRx7efp7U0C<br /><br />As noted in the abstract:<br />'We dispel with “street wisdom” regarding the practical implementation of Strassen's algorithm for matrix-matrix multiplication (DGEMM). Conventional wisdom: it is only practical for very large matrices. Our implementation is practical for small matrices. Conventional wisdom: the matrices being multiplied should be relatively square. Our implementation is practical for rank-k updates, where k is relatively small (a shape of importance for libraries like LAPACK). Conventional wisdom: it inherently requires substantial workspace. Our implementation requires no workspace beyond buffers already incorporated into conventional high-performance DGEMM implementations. Conventional wisdom: a Strassen DGEMM interface must pass in workspace. Our implementation requires no such workspace and can be plug-compatible with the standard DGEMM interface. Conventional wisdom: it is hard to demonstrate speedup on …'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-89805079646639162542022-10-20T09:28:02.237-05:002022-10-20T09:28:02.237-05:00I believe that Strassen's algorithm is of inte...I believe that Strassen's algorithm is of interest, including in practice, due to its cache-friendly properties, that is, it has better locality of memory accesses. A co-worker building a system used Strassen's algorithm for this reason, to speed up his code. There was (independently) a theoretical analysis, in the framework of cache-oblivious algorithms. This may be the right reference.<br /><br />Frigo, M., Leiserson, C. E., Prokop, H., & Ramachandran, S. (1999, October). Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039) (pp. 285-297). IEEE.<br />Ken Clarksonnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39344385633209654592022-10-15T16:07:22.749-05:002022-10-15T16:07:22.749-05:00Fawzi et al.'s new algorithm does work in GF(2...Fawzi et al.'s new algorithm does work in GF(2^k). In fact it works in any ring of characteristic 2 as it just relies on the property 1+1=0.Curtis Brighthttp://www.curtisbright.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35021486247969976572022-10-14T04:38:43.891-05:002022-10-14T04:38:43.891-05:00(I was the previous anonymous.) After more thought...(I was the previous anonymous.) After more thoughts and digging in the literature and code, a better answer for the problem of 2^n×2^n, which is actually not a problem at all! There are several ways to deal with it:<br />- standard padding, as mentioned before, and this sort of works;<br />- virtual padding, introduced in the 1990's, where the padding is not really done, but some data structure is responsible for it → this also sort of works;<br />- dynamic peeling: each time you have to split your matrix in four, if n is odd you ignore the last rows and columns, and compute the missing part "by hand";<br />- static peeling (which seems to be the best): for an instance of size n×n, you remove the last columns and rows to get a power of two, and then you compute the missing part (note that you can again do the same thing on this missing part).B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29341948561828704302022-10-13T15:59:53.924-05:002022-10-13T15:59:53.924-05:001) I thought that Strassen only working on 2^n x 2...1) I thought that Strassen only working on 2^n x 2^n would be a big problem. Why isn't it?<br /><br />→ I do not really know, but since Strassen's alg really provides some asymptotic improvement, the factor 2 lost by padding with zeroes is maybe not too expensive. Another possibilities is to track down these zeroes to avoid useless computations at the leaves of the recursion tree. (Note that in practice, computation are reverted to classical mult. for small matrices.)<br /><br />2) Is the new algorihtm enough better than Strassen to replace it i systems? To be used in new systems?<br /><br />→ The first big caveat is that the new alg. is for GF(2) only. And nobody's really interested in that case, or use different techniques that are not Strassen-like. So I suppose it won't be used. Yet I know for sure that some people working in this area have a look at the new alg to check whether standard techniques may extend it to other field (for instance GF(2^k)) where it may be interesting.<br /><br />Some last comments: <br />- For the misconception, you may be right that it used to be unpractical (but I was too young!) and that people did not update their knowledge on this. Also, Strassen alg is complicated for numerical computations, this may explain also: If the alg is mostly used in exact computations, many people won't be aware of it. Finally, I've heard that Knuth said (or wrote?) at some point that Strassen alg. is and will remain unpractical. And it is hard to argue against him ;-). <br />- You write in an answer to DJL that "[the new alg] was discovered by a program which is interesting." I agree that it is interesting. Though it is a pity that the authors suggest that it be the first (or one of the first) time this happens. In this area precisely (small matrix multiplications) and in other, this is routinely done! For instance, this catalogue has a lot of computer-invented algorithms for matrix multiplication: https://fmm.univ-lille.fr/.<br /><br />(A general impression on the "new" result: There are some quite interesting finding, but not that impressive (cf. the improvement in two days by humans). The technique of deep learning for this task is new, but other computerized methods already existed and the new technique is not really better. It may be even worse: Older methods with the same computational power as DeepMind has may provide better results! I cannot understand why this deserved a paper in Nature...)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-67886345258924306342022-10-10T22:51:55.058-05:002022-10-10T22:51:55.058-05:00Thanks!Thanks!DJLhttps://www.blogger.com/profile/04036156397398405817noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20707427357855045862022-10-10T21:38:02.883-05:002022-10-10T21:38:02.883-05:00My understanding is that 4-by-4 result holds only ...My understanding is that 4-by-4 result holds only for fields of characteristic 2. This is an interesting result, but not as general as Strassen or other well-known matrix multiplication algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12199239758336505402022-10-10T16:40:38.323-05:002022-10-10T16:40:38.323-05:00The fact that you can multiply two 4x4 matrices wi...The fact that you can multiply two 4x4 matrices with 47 mults is NEW. And it was discovered by a program which is interesting. <br /><br />This leads to a Strassen-like Matrix Mult algorithm algorithm that runs in time n^{2.777...} steps. This does NOT beat the current best-known bounds; however (informally) it is the best SIPLE algorithm known for time. Is it faster in practice? From the comments that tell be Strassen IS used and IS faster than the standard algorithm, its POSSIBLE that the new algorithm is better than Strassen. But since it was just discovered recently I doubt its been tried yet. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54246247462952745952022-10-10T14:39:39.429-05:002022-10-10T14:39:39.429-05:00Sorry: What I was trying to ask without grinding m...Sorry: What I was trying to ask without grinding my usual axe is: what's the story with the algorithm from the Google AI group? Is it really new? Is it really faster?DJLhttps://www.blogger.com/profile/04036156397398405817noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43792405292491983672022-10-10T12:06:00.043-05:002022-10-10T12:06:00.043-05:00Strassen wasn't practical on computers when it...Strassen wasn't practical on computers when it was discovered/invented. That's because the computers of the late 60s and early 70s had very limited support for recursion, and it often incurred a major performance hit as well. To borrow a useful term, highly recursive, memory intensive algorithms were "Galactic" on such hardware.<br /><br />Basically, heavily recursive code would require more RAM at peak use that those early machines had, because the resulting execution stack for the program would grow too deep. Remember, each stack frame of the program stack has a minimum (usually fixed) size, each recursive invocation grows the stack by 1 frame, and these machines had RAMs measured in Kilobytes. Even modestly stateful recursive code could easily "blow the stack".<br /><br />On many machines there were various tactics for getting your program to work despite the highly limited RAM. But most of these involved refactoring to avoid recursion, and breaking up your program so that only portions of it ever had to be in memory at any given time. Strassen was highly nontrivial to implement at all in such environments, and even if you did (or could), the resulting code wouldn't actually be faster for the inputs the machines could handle. <br /><br />To borrow a useful term, Strassen's algorithm was "Galactic" when he invented it. And that initial impression apparently persists even decades after it became widely used in production software. It's a great example of how an algorithm's practicality isn't just determined by its inherent space or time complexity, but also the strengths & limitations of the available computers that might run it.zyezeknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30113951494201469062022-10-10T10:25:33.477-05:002022-10-10T10:25:33.477-05:00(This is a response to all of the comments that po...(This is a response to all of the comments that pointed out that YES Strassen IS practical and IS used.) THANKS for the info- I should have phrased the post as QUESTIONS `is Strassen practical? Is Strassen used?' rather than presuppose that it is not practical or used yet. <br /><br />B above asked the question of WHY is the misconception about Strassen so widely held? Some speculation and question: WHEN did Strassen begin being practical? Used? I suspect there was a long time when it was NOT practical or used and some people (I am one of them) do not update their `everyone knows X' part of their brain often enough. And the DIVIDE between theory and practice and the lack of communication between the two is also a factor.<br /><br />Two more questions<br />1) I thought that Strassen only working on 2^n x 2^n would be a big problem. Why isn't it?<br /><br />2) Is the new algorihtm enough better than Strassen to replace it i systems? To be used in new systems? <br /><br />gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72708146248311805712022-10-10T10:19:30.488-05:002022-10-10T10:19:30.488-05:00The article said that Strassen is the most efficie...The article said that Strassen is the most efficient ``on most matrix sizes''- I think that can be interpreted correctly as that Strassen works well on matrices of sizes actually encounters. The algorhtms that are `much better' that I refer to would only be better for matrices of galactic size. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29634306809595405962022-10-10T08:34:11.352-05:002022-10-10T08:34:11.352-05:00For years in my algorithms class, I have given a h...For years in my algorithms class, I have given a homework assignment to find the cut-off point in recursion when one should switch from Strassen's algorithm on powers of 2. In languages like C, students would find the cross-over point at 32 or 64 depending on their coding efficiency. More recently in Java with object-oriented programming where matrices are represented as a pointer to a vector of pointers to column or row vectors, the scale and variation of student answers is much larger (128 to 1024 for the cross-over). Strassen's 2008 Knuth Prize citation (https://www.acm.org/media-center/2008/october/acm-sigact-2008-knuth-prize-recognizes-strassen-for-contributions-to-efficient-algorithm-design) you will see the sentence: "It is an intricate yet simple algorithm that remains the method of choice for multiplying dense matrices of size 30 by 30 or more on machines today."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82206188712269034352022-10-10T07:09:22.140-05:002022-10-10T07:09:22.140-05:00Your initial assumption is plain wrong! Strassen a...Your initial assumption is plain wrong! Strassen algorithm IS used, for years, in software libraries. There are two world though: In exact computation (over the integers, finite fields, etc.) Strassen is routinely used, cf Flint, FFLAS-FFPACK, M4RI, etc. In floatint-point computation, Strassen's algorithm may suffer from numerical instability so it is probably less used, but some libraries use it. <br /><br />This misconception about Strassen's algorithm is very common, I do not know why...B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11955068888183164012022-10-10T07:06:59.906-05:002022-10-10T07:06:59.906-05:00Does your "Much better is known" comment...Does your "Much better is known" comment and reference mean that the New Scientist article is technically incorrect???<br />DJLhttps://www.blogger.com/profile/04036156397398405817noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55851017939749992032022-10-10T03:31:49.926-05:002022-10-10T03:31:49.926-05:00Strassen's algorithm is routinely used in Comp...Strassen's algorithm is routinely used in Computer Algebra; see for instance . There is quite a bit of work on floating-point matrix multiplication using Strassen's algorithm as well (e.g., ), but I don't know if it has made its way into standard packages.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51518947647585989932022-10-10T01:03:03.838-05:002022-10-10T01:03:03.838-05:00About #2: Сonvolutional layers in CNN models requi...About #2: Сonvolutional layers in CNN models requires multiple multiplications of matrices of fixed size, this size if defined by kernal size of convolutional layer, typically 3x3, 5x5 or 7x7. And there is no sparsity in it. So the algorithm like Strassen (or the new one) could give a noticible speed-up for CNN inference engines. Lev Afraimovichhttps://www.blogger.com/profile/06192968736480644047noreply@blogger.com