9 ms·
The FBHHRBNRSSSHK-Algorithm for Multiplication is still not the end
- ajkjk 4y agoI'm really interested to know when we will be able to prove that we have the fastest algorithm for some matrix multiplication problem. Is there a theoretical lower bound? (well in this case, for 5x5, there's gonna be an actual lower bound. but for asymptotic cases..?) Is figuring out the theoretical lower bound some kind of undecidable/NP problem? what do we know about it?
- ithinkso 4y agoI think there is some educated-believe that it can be done in n^(2+epsilon) but not in n^2. No proof yet ofcourse
- genpfault 4y agohttps://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication#Lower_bounds_for_%CF%89 https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
- imbusy111 4y agoObviously a lower bound is O(N*M), but it's not very useful. But I'm not aware of any tighter lower bound.
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- klyrs 4y agoA lower bound of O(n^2 log n) has been known for quite some time. Good luck going any tighter than that... https://eccc.weizmann.ac.il/report/2002/012/download/ https://eccc.weizmann.ac.il/report/2002/012/download/ [pdf]
- 3j0hn 4y agoThis is a little bit apples and oranges, however. An asymptotic bound on the complexity doesn't say a lot about the number of multiplications needed for a fixed value of n=5 say. A lot of those complexity proofs say "for large enough n".
- klyrs 4y agoNot so! The 5x5 multiplication can be applied recursively to NxN matrices -- at the top level the "5x5 multiplication" carves the matrix into a 5x5 grid of "blocks" each of size approximately (N/5 x N/5). It's been a while since I've done this sort of complexity analysis, but I found some nice slides here explaining how to use the so-called Master Theorem for recursive algorithms: https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3-4.pdf https://www.inf.ed.ac.uk/teaching/courses/ads/Lects/lecture3... [pdf]
- 3j0hn 4y agoOh yeah, great point. Like plugging numbers into the master theorem, if 5x5 could be done in 25 multiplications, say, it would imply multiplication in O(n^2), and even 45 multiplications would give a new asymptotically fast multiplication. I would have to dig out a textbook to figure out what an Omega(n^2 log n) lowerbound would imply for n=5. edit of course wikipedia links to a explicit lowerbound which is kind of useful for small cases. https://www.sciencedirect.com/science/article/pii/S0885064X02000079 https://www.sciencedirect.com/science/article/pii/S0885064X0... has it as 2*n*m+2*n-m-2 which is 53 for m=n=5, which is not super tight, but tight enough to say that no 5x5 formula is ever going to lead to an asymptotically faster MM algorithm.
- henrydark 4y agothat's for real and complex fields, and it's not exactly that. I don't think there's anything better than O(n^2) with no conditions
- klyrs 4y agoah, excellent point
- Traubenfuchs 4y agoHow would one go about finding new ways to multiplicate matrices? Trial and error? Can the process be automated? Genius gets hit on the head by an apple moment?
- klyrs 4y agoFor small n, you can reasonably brute-force all (n x n) multiplication formulae in characteristic 2 because there's a naive bound on the number of element multiplications and the coefficients are binary. As n gets large (say, n>3?), the cost of brute-force becomes prohibitive. Beyond brute-force, I imagine that this problem could be phrased as a max-sat problem, mixed-integer linear program or similar. There are generic solvers that can get solutions for problems of moderate size. But unless it's a fairly rote translation to the solver's native representation, it's often better to write a custom solver and port heuristics into the notation native to the problem. As far as I understand it, that's the approach that the Fawzi et al and TFA took.
- js8 4y agoI was wondering, why use Deepmind when you can just use SAT solver? I am not saying SAT solvers cannot be improved with AI, maybe they can.
- klyrs 4y agoNote my uncertainty about the suitability of a max-sat formulation. But also note who did the Fawzi et al result: the DeepMind team at Google. I think that dogfooding their own stuff is an understandable default.
- fcholf 4y agoActually, this has been done: https://arxiv.org/abs/1903.11391 https://arxiv.org/abs/1903.11391
- Jabbles 4y agoSee https://news.ycombinator.com/item?id=33096580 https://news.ycombinator.com/item?id=33096580
- Sharlin 4y agoThe cryptic "5x52" in the title should be $\mathbb{Z}_2^{5\times5}$. Not sure how best to phrase that in plain text, but at least it shouldn't be "5×52".
- raverbashing 4y agoZ_2^(5x5) might be a better description (or, better, 5x5 matrices of binaries)
- Sharlin 4y agoOr "5x5 bit matrices".
- deleted 4y ago[deleted]
- mminer237 4y agoSomething like ℤ₂⁵×⁵?
- jwilk 4y agoThe multipication sign should be in superscript, but unforunately there's no suitable Unicode character… unless we abuse IPA: ℤ₂⁵ˣ⁵
- jeffbee 4y agoThis is a bit like the way that Bannister broke a decade-old record with his 4-minute mile, then someone beat his record 6 weeks later.
- harveywi 4y agoEven more impressive considering that the universe is expanding. So everyone today has to run farther in even less time.
- tiborsaas 4y agoMatter is not expanding with space, the forces between atoms are much stronger, so planets stay as-is over time. Instead think of space between galaxies expanding.
- ncmncm 4y agoI can't even think of the space between galaxies as they are now.
- yarg 4y agoI think he was joking.
- thehappypm 4y agoHow can both of those be true?
- pixl97 4y agoGravitational binding at a local level is stronger than the metric expansion of space. In the vast voids between galaxies it has a pronounced effect.
- mrpopo 4y agoYou can imagine that the space between matter particles is expanding, but since the binding forces between them are much stronger, they come back to the same relative positions. Only at scales where gravitation/electromagnetic forces have little to no influence you will be able to see things drifting apart
- telotortium 4y agoAbstract: "In response to a recent Nature article which announced an algorithm for multiplying 5×5-matrices over ℤ2 with only 96 multiplications, two fewer than the previous record, we present an algorithm that does the job with only 95 multiplications." The "recent Nature article" is, of course, Deepmind's reinforcement learning-guided search for better matrix multiplication algorithms: https://news.ycombinator.com/item?id=33096580 https://news.ycombinator.com/item?id=33096580. They improved upon Deepmind's algorithms by applying a method of their own, which is not described in this paper, but which they will publish in an upcoming paper: "Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. in preparation."
- ckemere 4y agoDeep-learning-hype-hater-quick-take: Based on that title (and a glance at the paper), my guess is that rather than brute force and megawatts of GPU power, they found a first-principles solution.
- inasio 4y agoOn that Google Nature paper, I'm not sure if the 5x5 matrix improvement is the more significant result, or that they figured out a way to optimize directly to SIMD/AVX instructions, resulting in faster execution even if not necessarily fewer operations
- ncmncm 4y agoThe result is not interesting for ordinary numbers, where the classical ("slower") method is faster. When each element of the 5x5 matrix is itself a matrix, it could be important. So AVX ops for the method are not interesting.
- bodhiandphysics 4y agoNo... using divide and conquer matrix multiplication with this gives n^2.83. Strassens algorithm is n^2.79. This is good fir 5 by 5 matrices... which are not terribly interesting.
- alexmolas 4y agoI love how advances in modern approaches (deep learning) push for advances in classical approaches. Something similar happened in physics, where advances in quantum algorithms made researchers to find better classical algorithms. Science is not a competition!
- robbomacrae 4y agoMy admittedly less charitable take is that they may have been sitting on this 1 operation optimization for a while, noticed it works on the new method, and only decided to go public now they have seen the positive reception and potential of such collaborations.
- kcexn 4y agoMore likely, I think it's that the first principles approach they have used to find this optimisation has applications in domains far outside of optimising matrix multiplications. Only because the Google paper crossed their desk did they even think to try it on matrix multiplications. And then more or less by luck, it happened to turn out to be slightly better. If it had produced exactly the machine learning algorithm, it would have been less interesting. The speed of the response makes me feel that the authors are extremely good at their domain, and that finding this algorithm was a reasonably trivial problem for them. The slowness of the follow up paper, I believe is that the authors understand that their mathematical domain is wildly far outside of what most people can easily understand, so they're going to take their time to write it up well, instead of drop a whole bunch of maths definitions that nobody else in the world understands.
- mattkrause 4y agoThe authors were already working on other small-matrix optimizations. They have a 2020 preprint about choosing good pivots for up to 8x8 matrices. https://arxiv.org/abs/2006.01623 https://arxiv.org/abs/2006.01623
- woopwoop 4y agoThat seems fine to me. What's so sinister about that?
- alexmolas 4y agoBesides from the reduction from 96 to 95 multiplications it would be interesting to know how have they derived these results. I think it's more interesting and has more impact to know the methodology they followed than just to know the algorithm.
- metahost 4y agoAside: what's on with the name of the algorithm? -- does it stand for something?
- deleted 4y ago[deleted]
- robinhouston 4y agoIt's the initials of the authors of the Nature paper
- metahost 4y agoAh gotcha, thanks!
- briga 4y agoPretty terrible name for an algorithm to be honest. Besides being unpronounceable, if the purpose is to acknowledge the discoverers of the algorithm it doesn’t even do a good job of that (who recognizes initials anyway?)
- nextaccountic 4y agoWhere's the proof that those algorithms works for all 4x4 and 5x5 matrices? An induction proof or anything else would suffice