5 ms·
Ninth Dedekind number discovered: long-known problem in mathematics solved
- jayhoon 3y agoInterestingly, the same result has been achieved by a single person, Christian Jäkel of TU Dresden: https://arxiv.org/abs/2304.00895 https://arxiv.org/abs/2304.00895
- HappyPanacea 3y agoAlso, He used 5311 Nvidia A100 GPU hours and the team in the article used 47000 Intel Stratix 10 GX 2800 FPGA hours.
- lgats 3y agoIntel® Stratix® 10 devices deliver up to 23 TMACs of fixed-point performance and up to 10 TFLOPS of IEEE-754 single-precision floating-point performance. Nvidia A100 GPU Double-Precision Performance: FP64: 9.7 TFLOPS, FP64 Tensor Core: 19.5 TFLOPS From my naive perspective, it would appear Christian's model was almost an order of magnitude more optimized?
- mafuy 3y agoThere are no floating point operations involved here though
- VonTum 3y agoHi, I'm Lennart, the author of the FPGA paper. You can't really compare them on a FLOPS basis. Firstly because our and Jäkel's algorithms are completely different. In fact within the FPGA accelerator itself we don't even use a single multiply, all our operations are boolean logic and counting. Whereas Jäkel was able to exploit the GPU's strong preference for matrix multiplication. All his operations were integer multiplications. In fact, in terms of raw operation count, Jäkel actually did more. There appears to be this tradeoff within the Jumping Formulas, where any jump you pick keeps the same fundamental complexity, with even a slight preference towards smaller jumps. It is just that GPU development is several decades ahead of FPGA development, thanks to ML and Rendering hype, which more than compensates for the slightly worse fundamental complexity. As a sidenote, raw FLOP counts from FPGA vendors are wildly inflated. The issue with FPGA designs is that getting this theorethical FLOP count is nigh-impossible, because getting all components running at the theorethical clock frequency limit is incredibly difficult, compare that with GPUs, where at least your processing frequency is a given.
- versteegen 3y agoHello, thanks for taking the time to reply here! My own Master's thesis was also about optimising and implementing algorithms to count certain (graphical) mathematical objects, but you picked a much more famous problem than me. I'm very surprised I didn't know the definition of Dedekind numbers, although it's related to things I touched on. I'm not too familiar with FPGAs but hope to have a use for them some day. Measuring their performance in FLOPs seems strange. How close to those theoretical limits does one typically get? Are there are a lot of design constraints that conspire against you, or is it just that whatever circuit you want can't be mapped densely to the gate topology?
- bazzargh 3y agothe van Hirtum paper now refers to that one as confirmation of its result https://arxiv.org/abs/2304.03039 https://arxiv.org/abs/2304.03039 beaten to the punch by a couple of days!
- Pulcinella 3y agoTL;DR it's: 286386577668298411128469151667598498812366
- juujian 3y agoThanks, I really didn't want to know the story, just really urgently needed the number :D
- kriro 3y agoI'm curious how does credit work in these situations? Is it first to upload/publish somewhere (arvix) or is it "here are the logs when we found it"? If it's the former, I'd build a pipeline that autogenerates a quick paper and uploads immidiately when the number is spit out. If it's the latter, how do we make sure the logs are not tampered with? Either way it's fun for me that one of the teams used the Noctua 2 cluster, I was in the server room a couple of month ago. Looked very underwhelming but it's quite interesting because I've never seen an FPGA cluster before. They are also doind some interesting ML things there (optimizing for power consumption). Edit: nevermind the first part, I read the van Hirtum paper and they registered the number in Github. Can't find any other time mentioned in the Jäkel paper.
- nsajko 3y agoOEIS, for example, seems to give more weight to Jäkel, I guess because Jäkel beat the other team to Arxiv by a few days.
- VonTum 3y agoLennart here, While Noctua 2 is certainly not one of the larger clusters out there, it does stand out as one of the only FPGA superclusters in Europe. This is the unique capability that made our project possible there. And yes, assigning unique credit in this case isn't trivial. I think that the only good answer here is: "It was discovered Simultaneously, independently"
- znpy 3y agoDumb question: what does this finding means for practical applications?
- ColinWright 3y agoSomeone always asks this, and it's been answered many times before. In short: this specific result probably has no practical applications just now. But there are several points to consider: 0: The techniques developed to answer the question might be useful for other applications; 1: It can be fun to chase down problems like this; 2: Sometimes results like this end up being useful decades, even centuries later; 3: The skills the researchers develop might be able to be used on other problems; 4: Not everything has to be useful. Consider music, art, hobbies. As examples of some of these: a: Elliptic curves were initially studied purely out of curiosity. Now they form the basis of modern cryptosystems; b: Factorising Integers was regarded as the pursuit of cranks, until it became an important tool in breaking cryptosystems; c: Latin Squares and Lattices were studied well before they were suggested as a possibility for post-quantum cryptography; d: Graph Theory was chased purely because it was interesting, and now forms the foundation of a gazillion algorithms; e: Eigenvectors were studied purely out of curiosity, then suddenly they became the basis of the Page Rank algorithm; f: Non-Euclidean Geometry was created purely to show that classic geometry was probably right, then showed it was actually "wrong", then turned out to be useful in relativity. And so on. There are more, and thousands, possibly millions of words have been written on the subject of how pure research, pursued simply because it was interesting, has turned out (in some cases!) to be useful. The 9th Dedekind number is unlikely to be useful, but its pursuit may be valuable in ways we can't imagine.
- znpy 3y agoThanks for the wall of text, I don’t doubt basic research is valuable and never wrote anything like that, so you could have saved that typing. > The 9th Dedekind number is unlikely to be useful, but its pursuit may be valuable in ways we can't imagine. The fact that you can’t imagine it doesn’t mean somebody else can’t imagine it. If you can’t imagine it, save the typing and let somebody that can imagine it reply, next time. Btw your reply was useless.
- vlovich123 3y ago> The problem: The calculation of these terms on normal processors is slow and also the use of GPUs as currently the fastest hardware accelerator technology for many AI applications is not efficient for this algorithm. > https://arxiv.org/pdf/2304.03039.pdf https://arxiv.org/pdf/2304.03039.pdf At this rate, a single FPGA processes about 5.2 α values per second, taking 47’000 FPGA hours to compute D(9) and > https://arxiv.org/pdf/2304.00895.pdf https://arxiv.org/pdf/2304.00895.pdf The only thing left to say is that we run the algorithm on Nvidia A100 GPUs. 5311 GPU hours and 4257682565 matrix multiplications later, we got the following value for the ninth Dedekind number Does this mean that Christian Jäkel developed a new technique? Or was this extending the existing P-coefficient formula work and making it work on GPUs?
- HappyPanacea 3y agoIt does seems so, both seems to compute the Dedekind number by using sums over equivalence classes of lower number of variables functions. Before [0][1] It was only possible to compute D(n+2) from Rn and Jäkel gave way to compute D(n+3) and D(n+4) from Rn and that seems to be major speed improvement. The D(n+3) computed D(8) in 17.56s, he couldn't use the same method for presumably because R(7) is 30,000 times R(6) and he is using matrix multiplication so it will take stupid long. Edit: I didn't read carefully enough, it is not new at all see [2] or [3] for examples. [0]: Yusun, T.J.: Dedekind numbers and related sequences (2008) page 19 [1]: Lennart Van Hirtum. A path to compute the 9th dedekind number using fpga supercomputing. https://hirtum.com/thesis.pdf https://hirtum.com/thesis.pdf, 2021. KU Leu- ven, Masters Thesis page 51 "While it would be nice to pick k = 3 and just compute D(9) from the structure of 6, at this time no efficient methods exist for computing P(n,k,α,β) for k ≥ 3. So we have to use k = 2" [2]: F. a Campo, Relations between powers of Dedekind numbers and exponential sums related to them, J. Integer Seq. 21 (2018), article 18.4.4, https://cs.uwaterloo.ca/ https://cs.uwaterloo.ca/ journals/JIS/VOL21/Campo/campo3.pdf and https://cs.uwaterloo.ca/journals/ https://cs.uwaterloo.ca/journals/ JIS/VOL21/Campo/campo3-corrigendum.pdf. [3]: Pieter-Jan Hoedt, Parallelizing with MPI in Java to Find the ninth Dedekind Number, preprint, 2015 https://web.archive.org/web/20150911060239/http://people.cs.kuleuven.be/~bart.demoen/WVKULAK/firstdraftofPaper_Hoedt.pdf https://web.archive.org/web/20150911060239/http://people.cs....
- Aardwolf 3y agoDoes this fully close a long-known problem, or is there now the next problem of finding the tenth Dedekind number D(10)?
- Someone 3y agoThat sequence is infinite. So, the next to fall most likely is D(10), then D(11), etc. I added “most likely” because I cannot rule out some mathematical result that makes it easier to compute some values for larger n.
- nsajko 3y agoThe entry for the Dedekind numbers in the On-line Encyclopedia of Integer Sequences (OEIS): https://oeis.org/A000372 https://oeis.org/A000372
- deleted 3y ago[deleted]
- Carolin48 3y agoHi Christian and Lennart - if you are still listening in here... Did you know the other guy was working on the same problem - have you ever met before? Lennart through his master thesis has a track record on working on the thing, Christian I am not sure, haven't seen any previous publication yet. It is sort of funny that the number was computed practically simultaneously some 450 kms apart (though it happens in science, as if there is something in the air sometimes ;-) Also, it has now been stated that D(9) "may be the last in the sequence that is feasible to discover" (The New Scientist) - is this a view you can share? (Never say never, I know :-)