Timeline for Upper bound on the number of permutations in a set during an algorithm
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 8, 2017 at 1:07 | comment | added | Matt Samuel | @Gerhard I made a massive speed optimization and afterwards it occurred to me to try to accurately estimate how long it would take to calculate $n=16$. ,I got 13 years. Looks like we're going to have to try to parallelize it. | |
| Dec 6, 2017 at 20:54 | comment | added | Gerhard Paseman | Indeed. By differential encoding (which is probably close to what you are using), you can reduce the storage further. But you have been working on this a while and probably have considered most of the possibilities for representation. Gerhard "May There Be No Error" Paseman, 2017.12.06. | |
| Dec 6, 2017 at 20:46 | comment | added | Matt Samuel | @GerhardPaseman Thanks. I think I've actually come up with the minimum possible space usage and that ends up being 87TB (assuming a constant of 0.275). It doesn't store the permutations at all. It uses the rank in lexicographical order as an index into a paged array, so 16 bytes per permutation, give or take an extra megabyte. Theoretically you could arrange it so that the actual space usage is terrible because they're spread out across pages, but they actually seem to cluster together pretty nicely, and I've been able to get n=13 in 13GB of memory, which is available to me. | |
| Dec 6, 2017 at 15:55 | comment | added | Gerhard Paseman | Of course, I should add that for n=16, the constant is above 0.266666 (4/15), so it looks like you need to rearrange memory usage, perhaps writing to disk. Gerhard "Good Luck With Massive Computation" Paseman, 2017.12.06. | |
| Dec 6, 2017 at 0:21 | vote | accept | Matt Samuel | ||
| Dec 2, 2017 at 1:27 | comment | added | Matt Samuel | @fedja It's not a secret. It's actually the iterative version of the Maple code on the sequence web page (which is recursive). You take the value at the node you remove and add it to the values at the nodes you add, with a sign of $(-1)^{|B|}$. The value at the identity is $1$ in the first step. The result is the final value at the longest element. | |
| Dec 2, 2017 at 0:05 | comment | added | fedja | @MattSamuel Interesting. If we have such a clear idea of what $A_K$ are at least sometimes, why should we keep all their elements in the memory in the literal sense? If not a secret, how does your algorithm use them? | |
| Dec 1, 2017 at 20:21 | comment | added | Gerhard Paseman | You're welcome. I recommend trying n=7 and n=8 and checking my characterization of A_jm. If I have it right, you can probably use it to speed up your computation of M16 as well. Gerhard "Don't Call It A Monster" Paseman, 2017.12.01. | |
| Dec 1, 2017 at 20:05 | comment | added | Matt Samuel | Thanks. I'm actually trying to compute $M_{13}$ because I realized there's a way to do it using far less memory. | |
| Dec 1, 2017 at 18:52 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |