Some results from a live GNFS180 polsel

fivemack · 2009-12-05, 22:32

frmky and I have done the polynomial selection for EM43; c5 = 0 through 110000, on four GPUs (my GTX275 and three-quarters of frmky's Tesla S1070). It took about six GPU-weeks.

I think the Murphy_E bound somewhere around 2.7e-14 at 180 digits is significantly too low - we got about ten million polynomials in that range, and wouldn't have complained (although it would have taken several days to see the first polynomial) to get only the ones with E>4.0e-14, or even 4.5e-14. I'm the only person who can be blamed about this, since I set the bound in the first place, but I think it would be better to put it a bit higher.

I don't know how to go about shifting the stage-1 and stage-2 bounds in the face of evidence; is it possible to determine from a final polynomial what its scores at stage-1 and stage-2 were, or do I have to instrument msieve-gpu and run another large polsel? I suppose I can easily run 110k to 150k, it'll slow down the 2-941 linalg but not by all that much, and if we get an unexpectedly good polynomial before EM43 tasks start getting handed out, it's probably easy to change.

frmky · 2009-12-05, 23:40

For a few highly productive c5's, stage 2 ran for over 10 hours leaving the GPU idle. What probably should have been a 4-5 day run took nearly 8 days.

jasonp · 2009-12-06, 02:52

Raising the target E value and lowering the initial stage 2 norm will make the root sieve run much faster. It sounds like at a minimum stages 1 and 2 should run in separate threads; see the GPU thread for some musings on that.

PS: What do the best polynomials look like? Serge reported some experiments where the reported E value only weakly predicted how well a polynomial would find relations, and that a pol5 polynomial with a much better E value sieved significantly worse. Especially when a search produces hundreds of 'best' polynomials, maybe we should customize the factor base bounds in the E-value computation for the size of the polynomials, instead of using the same values all the time. We wouldn't be able to compare with pol5 anymore, but could probably sieve more effectively.

Batalov · 2009-12-06, 02:57

So what was the final best Murphy E?

And try "my" new (hopefully useful) formula to find an equivalent SNFS digit difficulty (fitted from a couple dozen jobs):

SNFS_equivalent_difficulty = -30 log_{[SIZE=1]10[/SIZE]}E - 128

What is your equivalent SNFS difficulty?
(For B+D gnfs-180, 2,2254L, a poly with 6.41e-14 suggests ~= snfs-268.
Msieve_144gpu, sadly, didn't produce any polys and died. 6.41e-14 is the pol51 poly.)

_____
I have finally figured out for myself what Murphy E means. It is proportional to the inverse of the total project sieving time. On the same machine or a cluster, a job with E=6e-14 will take fairly exactly 10x more time than a job with E=6e-13 and a 100x more time than a job with E=6e-12.

I'll write a separate thing about the quintics, quartics etc.: this measure helps to quantify the proverbial suboptimal-degree penalty.

jasonp · 2009-12-06, 03:06

Technically the E value is the probability that one sieve value will be smooth, given the sieving area and the factor base bounds. That probability goes up with increasing factor base bounds, and may go up or down as the sieving area increases. Both pol5 and msieve fix all of those parameters, so that E values across factorizations are all directly comparable.

Batalov · 2009-12-06, 04:46

tangential Re: posts #3 and #5.

Actually, pol51opt has hidden -f, -F, -A parameters which (if supplied and roughly correspond to the future sieving use) affect the E value towards incomparability (cf. post #5) _but_ the output polynomials eventually sieve better in real life, indeed!

I have more than once used these for the final polishing of the best candidates: for that, you put a few "*.51.m" lines that were the parents of the better initial offspring and repeat the pol51opt with somewhat increased search space plus the increased real-life -f, -F, -A values. This is similar to the suggested course in #3.

frmky · 2009-12-06, 06:42

The poly is

Code:

# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
skew: 536967657.44
c0: 486705885709926708065232033951307588813625602275
c1: 5584390886742987582391695130327092942465
c2: -2589293749660254385400621955533
c3: -205785074447711087191729
c4: -211349858750
c5: 101640
Y0: -77187904731145180346916804885190882
Y1: 27609235740881943367
n: 278490841076279407188741439481565179355926725853710201632331620642982062389901741890579963524423782637435949041666525000702723914662388812510545494307250950777886431051612811386531

so your formula gives 267.2 for a GNFS of 179.4 digits.

Batalov · 2009-12-06, 06:55

That's a great one. ...And look at that alpha!

(and you probably had even larger abs-value alphas!)

Could you please run (just for a day) our number?
It was posted here.

(you will observe that p and q are almost but just shy of 32-bit in size and resultant is 63.4 bits in size... some tricky carryovers crept in?)

jrk · 2009-12-06, 07:06

Is that a record alpha?

jasonp · 2009-12-06, 07:20

Some of the Bochum slides make it sound like spectacular alpha values like that would be common if you pour a great deal of effort into stage 2, and the input is very large so a big search space is available.

frmky · 2009-12-06, 08:29

That actually was the best alpha as well. The five best alphas were

Code:

# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
# norm 9.443674e-18 alpha -8.816673 e 6.512e-14
# norm 9.033319e-18 alpha -8.728573 e 6.310e-14
# norm 8.474841e-18 alpha -8.636510 e 5.865e-14
# norm 8.823795e-18 alpha -8.603598 e 6.228e-14

and the best E's were

Code:

# norm 9.833432e-18 alpha -9.052498 e 6.697e-14
# norm 9.443674e-18 alpha -8.816673 e 6.512e-14
# norm 9.033319e-18 alpha -8.728573 e 6.310e-14
# norm 8.823795e-18 alpha -8.603598 e 6.228e-14
# norm 9.606499e-18 alpha -7.836603 e 6.225e-14

Note the significant overlap. All 6 of these polys were found at c5 of 101640.

Quote:

Originally Posted by Batalov

Could you please run (just for a day) our number?
It was posted here.

Sure.

2009-12-05, 22:32	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 3×2,141 Posts	Some results from a live GNFS180 polsel frmky and I have done the polynomial selection for EM43; c5 = 0 through 110000, on four GPUs (my GTX275 and three-quarters of frmky's Tesla S1070). It took about six GPU-weeks. I think the Murphy_E bound somewhere around 2.7e-14 at 180 digits is significantly too low - we got about ten million polynomials in that range, and wouldn't have complained (although it would have taken several days to see the first polynomial) to get only the ones with E>4.0e-14, or even 4.5e-14. I'm the only person who can be blamed about this, since I set the bound in the first place, but I think it would be better to put it a bit higher. I don't know how to go about shifting the stage-1 and stage-2 bounds in the face of evidence; is it possible to determine from a final polynomial what its scores at stage-1 and stage-2 were, or do I have to instrument msieve-gpu and run another large polsel? I suppose I can easily run 110k to 150k, it'll slow down the 2-941 linalg but not by all that much, and if we get an unexpectedly good polynomial before EM43 tasks start getting handed out, it's probably easy to change. Last fiddled with by fivemack on 2009-12-05 at 22:33

2009-12-06, 02:57	#4
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	So what was the final best Murphy E? And try "my" new (hopefully useful) formula to find an equivalent SNFS digit difficulty (fitted from a couple dozen jobs): SNFS_equivalent_difficulty = -30 log_{[SIZE=1]10[/SIZE]}E - 128 What is your equivalent SNFS difficulty? (For B+D gnfs-180, 2,2254L, a poly with 6.41e-14 suggests ~= snfs-268. Msieve_144gpu, sadly, didn't produce any polys and died. 6.41e-14 is the pol51 poly.) _____ I have finally figured out for myself what Murphy E means. It is proportional to the inverse of the total project sieving time. On the same machine or a cluster, a job with E=6e-14 will take fairly exactly 10x more time than a job with E=6e-13 and a 100x more time than a job with E=6e-12. I'll write a separate thing about the quintics, quartics etc.: this measure helps to quantify the proverbial suboptimal-degree penalty. Last fiddled with by Batalov on 2009-12-06 at 03:07 Reason: 6.41e-14

2009-12-06, 06:55	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2·47·101 Posts	That's a great one. ...And look at that alpha! (and you probably had even larger abs-value alphas!) Could you please run (just for a day) our number? It was posted here. (you will observe that p and q are almost but just shy of 32-bit in size and resultant is 63.4 bits in size... some tricky carryovers crept in?) Last fiddled with by Batalov on 2009-12-06 at 07:07 Reason: /salivating on the keyboard doesn't do much good -- it shorts/

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
msieve polsel trouble on GTX1080Ti	fivemack	GPU Computing	2	2018-04-02 12:28
At least one upcoming paper on polsel	Dubslow	Msieve	0	2016-03-16 06:24
Feature request: multithreaded polsel	Andi47	Msieve	1	2010-02-20 01:16
bad parameters for 153-digit CPU polsel ?	fivemack	Msieve	8	2010-02-08 10:35
Software you just can't live without...	Xyzzy	Lounge	23	2004-09-10 23:41

2009-12-05, 23:40	#2
frmky Jul 2003 So Cal 844₁₆ Posts	For a few highly productive c5's, stage 2 ran for over 10 hours leaving the GPU idle. What probably should have been a 4-5 day run took nearly 8 days.

2009-12-06, 02:52	#3
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	Raising the target E value and lowering the initial stage 2 norm will make the root sieve run much faster. It sounds like at a minimum stages 1 and 2 should run in separate threads; see the GPU thread for some musings on that. PS: What do the best polynomials look like? Serge reported some experiments where the reported E value only weakly predicted how well a polynomial would find relations, and that a pol5 polynomial with a much better E value sieved significantly worse. Especially when a search produces hundreds of 'best' polynomials, maybe we should customize the factor base bounds in the E-value computation for the size of the polynomials, instead of using the same values all the time. We wouldn't be able to compare with pol5 anymore, but could probably sieve more effectively. Last fiddled with by jasonp on 2009-12-06 at 07:09 Reason: stage 2 norm goes down if minimum E goes up

2009-12-06, 03:06	#5
jasonp Tribal Bullet Oct 2004 DD7₁₆ Posts	Technically the E value is the probability that one sieve value will be smooth, given the sieving area and the factor base bounds. That probability goes up with increasing factor base bounds, and may go up or down as the sieving area increases. Both pol5 and msieve fix all of those parameters, so that E values across factorizations are all directly comparable. Last fiddled with by jasonp on 2009-12-06 at 03:09

2009-12-06, 04:46	#6
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×47×101 Posts	tangential Re: posts #3 and #5. Actually, pol51opt has hidden -f, -F, -A parameters which (if supplied and roughly correspond to the future sieving use) affect the E value towards incomparability (cf. post #5) _but_ the output polynomials eventually sieve better in real life, indeed! I have more than once used these for the final polishing of the best candidates: for that, you put a few "*.51.m" lines that were the parents of the better initial offspring and repeat the pol51opt with somewhat increased search space plus the increased real-life -f, -F, -A values. This is similar to the suggested course in #3.

2009-12-06, 07:06	#9
jrk May 2008 3·5·73 Posts	Is that a record alpha?

2009-12-06, 07:20	#10
jasonp Tribal Bullet Oct 2004 3·1,181 Posts	Some of the Bochum slides make it sound like spectacular alpha values like that would be common if you pour a great deal of effort into stage 2, and the input is very large so a big search space is available.