Parameter explorations for CADO 165-170 digits

[charybdis]

Originally Posted by bur

The yield per 5000 q varies quite strongly, just the last three workunits had 20273, 15446 and 17053, respectively.

This is normal, it's a consequence of the varying number of special-q within ranges of size 5000. The number of relations per special-q varies much less.

Incidentally, the number of special-q per range varies less when sieving on the rational side, so on the SNFS jobs that require this, the number of relations per WU does not have as much variation.

[bur]

I'm at 190M relations of which 69.7% or 132M are unique. The C167 took 152M uniques to build a matrix, what number of uniqes can I expect for a C170?

Is the necessary number of uniques just a function of log(n) or are there other influences?

And from comparison with that C167 the uniques ratio seems a bit low, what does it depend on? Just the q-range or also size/poly/...?

[VBCurtis]

Originally Posted by bur

And from comparison with that C167 the uniques ratio seems a bit low, what does it depend on? Just the q-range or also size/poly/...?

Random properties of the poly. No way to predict ahead of time what uniques ratio will be. However, as you note Q-range does influence uniques ratio. I am happy if I'm above 70% on a job.

I expect you'll need more uniques than you did for a C167, but I've no idea how many more- maybe 5%? 10%? There's a lot of noise here, too- your C167 with a different poly may have needed 150M or 155M, etc.

[bur]

So the poly influences the uniques ratio, but "random" meaning not depending on the score? Is the same true for the required number of uniques? This would mean that a slightly lower scoring poly could perform better overall?

I'm at 205M total and 143M uniques (69.8%). I'll wait another day, which should bring me to 220M total and 153M uniques, before attempting to build a matrix.

That would make it 14 days of sieving for the 220M. The C167 took 12 days until I could build a matrix, so it's actually going quite well.

Btw, if C165 to C170 will double the sieving time, what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for x^n?

[bur]

Curtis, you suggested excess of 0.05 for building the matrix with CADO. For msieve I think the same effect is achieved with target-density? What would be a good value? Charybdis used target_density = 100 for his c170 posted on the first page of this thread.

[charybdis]

Originally Posted by bur

Curtis, you suggested excess of 0.05 for building the matrix with CADO. For msieve I think the same effect is achieved with target-density? What would be a good value? Charybdis used target_density = 100 for his c170 posted on the first page of this thread.

The effect isn't exactly the same, though both can be used to ensure that the matrix you get isn't way too big. required_excess tells filtering not to try building a matrix if the excess is too small. target_density (in both msieve and CADO, though the values cannot be directly compared between the two) tells the merge process how dense a matrix it should try to build; denser matrices are smaller and therefore run faster, but more relations are required to build a denser matrix. The error "too few cycles, matrix probably cannot build" in msieve tells you that there weren't enough relations to build a matrix with the chosen target_density.

100 is probably sensible, though the optimum value for a given job depends on the ratio of sieving to LA speed for your system.

[bur]

Thanks, but msieve has no equivalent to required_excess?


The first attempt failed as expected. I had 154M uniques (the recent C167 took 152M):

Wed Jan 12 16:44:33 2022  keeping 41220401 ideals with weight <= 200, target excess is 216115
Wed Jan 12 16:44:36 2022  commencing in-memory singleton removal
Wed Jan 12 16:44:40 2022  begin with 39898507 relations and 41220401 unique ideals
Wed Jan 12 16:45:37 2022  reduce to 39629881 relations and 40951589 ideals in 21 passes
Wed Jan 12 16:45:37 2022  max relations containing the same ideal: 200
 Wed Jan 12 16:45:39 2022  filtering wants 1000000 more relations

Is it possible to estimate the number of required additional uniques from the relations:ideals ratio?

[VBCurtis]

Correct, msieve has no filtering equivalent to required_excess. We use target_density as a proxy.

Yes, you can estimate based on how early the filtering failed; but it's easier to just try filtering with a lower target_density (like default) rather than try to recall just how far away you might be based on your previous experience. That is, if a C165-175 filtering run usually has 12 filtering passes and yours failed on pass 1, you need quite a few more relations- but if it failed after pass 8 or 9, it nearly worked and an adjustment to target density or a few M more relations will get you a matrix.

[charybdis]

In this case filtering would have failed whatever target_density was used, because there were more ideals than relations. Once you have more relations than ideals and the excess is greater than the displayed target excess value, filtering will proceed until the merge phase - maybe if it's extremely tight it could fail earlier, but I've never seen that - and if target_density is too high you get "too few cycles, matrix probably cannot build". Before the merge begins, target_density is not used at all.

I wish there was an option to dump the output of clique removal to disk if merging fails, so that you could run merge at different TDs without having to go through all the earlier stages of filtering again...

[bur]

Second attempt with 230M rels and 162M uniques, it went through to the full merge, but quit there. So it's getting closer.

Btw, if C165 to C170 will double the sieving time, what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for an exponential relation?

[axn]

Originally Posted by bur

what is the time ratio between C167 and C170? I've been wondering that generally, interpolating within a linear relation is easy, but what is the rule for an exponential relation?

5 digits = factor of 2
1 digit = factor of 2^(1/5) ~= 1.15
3 digits = factor of 2^(3/5) ~= 1.52

Linear interpolation between 1 & 2 wouldn't be too far off though. You'd get 1.6 which is good enough for gov't purposes.