Some CADO-NFS Work At Around 175-180 Decimal Digits

[VBCurtis]

I view mfb and lambda both as methods to control the amount of wasted cofactor-splitting. For reasons unclear to me, CADO runs quite a bit faster (in extensive testing at 100-140 digits) with mfb set well below 2*lpb. I've been using lambda as a sort of floating-point control for mfb, and on small numbers I have lots of runs where changing lambda by 0.01 does change the yield per Q but also the number of relations needed (in the direction that suggests the job is effectively a smaller LP choice). I found that using LP choices 1 or 2 bits higher than traditional choices but tight mfb led to faster factorizations.

I suppose I won't be too surprised if that doesn't work at this size; 31/32 is pretty much traditional for this size of job, so perhaps a tight mfb or tight lambda setting is overly restrictive.

[charybdis]

c180 results:
Poly score 9.842e-14, within 2% of the score for the last c179.
65.1M CPU-sec sieving for 321M raw relations, 225M unique.
TD=110 produced a 16.6M matrix.

mfb0=59 doesn't seem worth it to me. Yield and rel/sec improve a few percent but so does the number of relations needed to build a matrix. More importantly, 59 gives bigger matrices than 58; I'd guess something like 8-10% more unique relations are needed at 59 to build a matrix comparable to what you'd get at 58.

There's one more c180 on the HCN list that's unambiguously a GNFS job (there are a couple that are SNFS 261/2, I suspect SNFS will be slightly faster there?) so I'll run it with mfb0=58 and lambda0=1.93 - intermediate between the previously tried 1.88 and CADO-default 58/31+0.1=1.97 - unless anyone has a better suggestion.

[VBCurtis]

I think 1.93 is an excellent idea.
mfb0=59 should produce a slightly larger matrix than 58, since more of the relations will have a largest-bit large prime. Sieving a few more relations should overcome that, but if that makes the sieving take longer than an MFB=58 job then it's a waste.

[charybdis]

Stats for c180 with lambda0=1.93:

Poly score 9.285e-14.
70.2M CPU-seconds sieving for 322M raw relations, 218M unique.
TD=110 produced a 15.8M matrix.

Poly is ~7% worse than the c179 that I ran with default lambda0 of ~1.97. Sieving is ~6% slower per raw relation but ~8% slower per unique relation, and the matrix ended up a little bigger too.

I doubt the poly scores predict sieving speed to the nearest 1%, but lambda 1.93 performs noticeably better than 1.88 and within a percent or so of 1.97. Suggests that the default 1.97 is close enough to optimal here that it's not worth trying to narrow it down further?

Next GNFS target in the HCN list is a c182. I'll keep most of the sieving params the same to get a direct comparison - experimentation can wait till the bunch of c184s if I decide to do them - but should lims go a bit higher? 105M/145M?

[VBCurtis]

Originally Posted by charybdis

I doubt the poly scores predict sieving speed to the nearest 1%, but lambda 1.93 performs noticeably better than 1.88 and within a percent or so of 1.97. Suggests that the default 1.97 is close enough to optimal here that it's not worth trying to narrow it down further?

Next GNFS target in the HCN list is a c182. I'll keep most of the sieving params the same to get a direct comparison - experimentation can wait till the bunch of c184s if I decide to do them - but should lims go a bit higher? 105M/145M?

If I were to do another test, I'd try mfb0=59 with a tighter lambda setting; but you've shown 59 is slower than 58, and with 58 that not specifying lambda is as fast as 1.93. Your params are simpler, and likely faster than trying to find a fastest-lambda with 59.

As for changing lims: larger lims will improve relations per Q and may improve uniques per raw relations ratio, but at the expense of a slightly larger matrix. The rule of thumb I've been using is to target an ending Q somewhere near lim1; so, if your C180 runs have ending Q near 130M, I'd add 10M to both lims for C182. I don't have theory to back this, and keeping lim smallish while running Q well above lim1 may be faster overall.
The larger the job, the more Q will exceed lim1; my rule of thumb has helped me in the 140-175 digit range.

[charybdis]

Originally Posted by VBCurtis

The rule of thumb I've been using is to target an ending Q somewhere near lim1; so, if your C180 runs have ending Q near 130M, I'd add 10M to both lims for C182.

The last c180 did indeed finish around 130M; the other numbers had slightly better polys and finished closer to 120M.

[charybdis]

Originally Posted by charybdis

A further trawl through the documentation reveals that a lambda of mfb/lpb + 0.1 is used if we leave it unspecified.

Despite what sieve/README.descent says ("in the first case, lambda defaults to mfb0/lpb0+0.1 as everywhere else in cado-nfs"), it looks like I was wrong, and presumably that readme file is outdated.

From sieve/las-norms.cpp:

    /* when lambda = 0 (automatic), we take mfb/lpb + 0.3, which is
       experimentally close to optimal in terms of seconds per relation
       (+ 0.2 might be even better on the rational side) */
    if (lambda == 0.0)
        lambda = 0.3 + (double) sc.sides[side].mfb /
            (double) sc.sides[side].lpb ;

So the default lambda0 for lpb0=31, mfb0=58 is actually 2.17 not 1.97. Probably worth trying ~2.05 on my next run then.

[charybdis]

c182 stats:

Poly score 6.643e-14.
98.0M CPU-seconds sieving (Q 20M-181.4M) for 321M raw relations, 218M unique.
TD=110 produced a 17.8M matrix.

The parameters are still holding up fairly well at c182 if we assume that the poly score is inversely proportional to difficulty; I don't know whether this is a good assumption to make.
The matrix has got bigger, as expected.
Final Q was well beyond lim1 so maybe lims could be higher, but before trying that out I'm going to test lambda0=2.07.

[charybdis]

The c183 stats below aren't directly comparable to those for the c182 above, for a couple of reasons.
Firstly, I ran the c183 on a slightly different set of machines, giving about a 1% speedup in CPU-time.
Secondly, one machine had some strange connection problems. I won't bother with the details, but the lowdown is that the server cancelled all the WUs from this client without receiving any relations. This meant that the final Q was a bit larger than it should have been, but the factorization will only have been slowed down by a fraction of a percent.

Poly score 6.356e-14 (4.5% worse than c182 above).
Sieved Q from 20M to 195.9M, with about 1.7M missing due to the bad client.
100.5M CPU-seconds for 321M raw relations, 218M unique.
TD=110 produced an 18.3M matrix. This is a bit bigger than the c182 matrix, but the all the figures looked very similar to the c182 run in the early stages of filtering, so I'm going to chalk the difference in matrix size up to the peculiarities of the polynomial.

Putting all the figures together, lambda0 = 2.07 (= mfb0/lpb0 + 0.2) might be 1% faster than the default (mfb0/lpb0 + 0.3). It looks like changing lambda from the default is unlikely to produce big gains at this size.

Next up will be the bunch of c184s. Would I be right in thinking lpb 32/32 deserves some testing here?

[VBCurtis]

Sorry for the delay, been busy with some data-gathering for nfs@home queue planning.

A params.C185 file should have the usual 25-30% increase in lim's, and we should test 32/32 against the current setting.

If we stay with 31/32, I'd add another 20-30M relations wanted. 32/32 should be 30% higher than that to start with.

Poly select should be about double the C180 file- say, 60% increase in admax and 25% increase in P.

Edit: I'd also raise qmin to 25M or 30M. The most recent CADO-factorization paper mentions that controlling the qmax/qmin ratio helps to control the duplicate rate; so as our jobs get tougher and sieve up to larger Q's, qmin should rise as well. If I understood what they said properly (a weak assumption), a ratio of 7 is a decent target, and duplicate-rates get poor once the ratio exceeds 10. We saw that back when I suggested qmin of 500k, and their paper agrees with the data you gathered. We expect Q-max of 175-200M, I think?

[VBCurtis]

I decided to copy the params from a few posts up and make the changes I just recommended. Simpler this way. Also, I changed ncurves0 to 25 from 20.
Draft params.c185:

tasks.I = 15
tasks.qmin = 30000000
tasks.lim0 = 125000000
tasks.lim1 = 175000000
tasks.lpb0 = 32
tasks.lpb1 = 32
tasks.sieve.mfb0 = 60 #maybe 59?
tasks.sieve.mfb1 = 90 #maybe 91 to improve yield?
tasks.sieve.ncurves0 = 25
tasks.sieve.ncurves1 = 13

rels wanted = 340000000

Here's the poly-select settings:

tasks.polyselect.P = 3000000
tasks.polyselect.admin = 2e4
tasks.polyselect.admax = 35e5
tasks.polyselect.adrange = 1680
tasks.polyselect.incr = 210
tasks.polyselect.nq = 15625
tasks.polyselect.nrkeep = 120 
tasks.polyselect.ropteffort = 35