Bad poly select estimates

Kvasir · 2021-04-06, 16:52

When I'm running YAFU and it switches to nfs mode after ECM, it has a habit of producing very optimistic estimates (or very bad performance) for number in the low 100's (100-110 digits or so). The following is an example of poly selection for a C100:

elapsed time of 3861.2958 seconds exceeds 128 second deadline; poly select done.

Why is this? On higher number the estimate is more correct, and the poly selection is often faster.

bsquared · 2021-04-07, 13:41

Quote:

Originally Posted by Kvasir

When I'm running YAFU and it switches to nfs mode after ECM, it has a habit of producing very optimistic estimates (or very bad performance) for number in the low 100's (100-110 digits or so). The following is an example of poly selection for a C100:

elapsed time of 3861.2958 seconds exceeds 128 second deadline; poly select done.

Why is this? On higher number the estimate is more correct, and the poly selection is often faster.

I have seen windows builds sometimes take super long on some poly ranges. I have no idea why that happens (yafu relies on msieve here) and it doesn't seem to happen using the linux build.

Assuming that's not the problem here, I would recommend using -psearch avg or -psearch good instead of the default poly search. These options stop as soon as an average (good) poly is found rather than using the timing table, which is in need of an update (especially for smaller C100-C110 numbers).

charybdis · 2021-04-07, 16:26

I think this revision to msieve may be partly responsible? Particularly "deadline_per_coeff = 8640000", which essentially means each leading coefficient is search-range-limited rather than time-limited, so yafu poly selection continues until each thread is done with its first coefficient which could take much longer than the deadline.

bsquared · 2021-04-07, 17:32

Quote:

Originally Posted by charybdis

I think this revision to msieve may be partly responsible? Particularly "deadline_per_coeff = 8640000", which essentially means each leading coefficient is search-range-limited rather than time-limited, so yafu poly selection continues until each thread is done with its first coefficient which could take much longer than the deadline.

Looking into that, thanks.

Here are example runs using a couple different poly search methods on a C100 on Linux. I will repeat this for windows since that seems to be where the problems are. I'm using my development source, but I think it's substantially the same as branches/wip.

with -psearch avg -threads 16

Code:


min E-value: 9.96e-09
poly select deadline: 638
time limit set to 0.18 CPU-hours
expecting poly E from 1.30e-08 to > 1.50e-08
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 9.999000e-09, new best line = 2
new best score = 1.058000e-08, new best line = 4
new best score = 1.074000e-08, new best line = 10
new best score = 1.167000e-08, new best line = 15
new best score = 1.229000e-08, new best line = 22
new best score = 1.266000e-08, new best line = 61
nfs: best score is currently 1.266e-08
nfs: found poly better than avg quality
elapsed time: 23.4539 seconds (1221 second deadline); poly select done
best poly:
# norm 1.329616e-13 alpha -4.762021 e 1.266e-08 rroots 2
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 518246.35
c0: 84865267905977794683633125
c1: -1981237361723192340991
c2: -2697204802913816
c3: 5458443142
c4: 12180
Y0: -578836284879405326839926
Y1: 13343770334947

RelProcTime: 76
BLanczosTime: 97
sqrtTime: 14
NFS elapsed time = 770.6109 seconds.

with -psearch fast -threads 16

Code:

elapsed time: 76.4923 seconds (76 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 9.999000e-09, new best line = 2
new best score = 1.058000e-08, new best line = 4
new best score = 1.074000e-08, new best line = 10
new best score = 1.167000e-08, new best line = 15
new best score = 1.229000e-08, new best line = 22
new best score = 1.266000e-08, new best line = 61
new best score = 1.428000e-08, new best line = 129

best poly:
# norm 1.695913e-13 alpha -5.449176 e 1.428e-08 rroots 0
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 460542.11
c0: 264364209926768035382073459
c1: 789976835377316218189
c2: -3043500066840224
c3: -5903074724
c4: 18480
Y0: -521548409549556316408492
Y1: 21442439626079

RelProcTime: 81
BLanczosTime: 112
sqrtTime: 39
NFS elapsed time = 785.6548 seconds.

So, -psearch avg ran poly search 3x faster and ended up with a slightly worse poly. But in the end the times were about a wash. In the first case it spent 3% of the time in poly search and in the second case about 10%. I think either of these is reasonable.

I'll repeat using windows and see if it's much different.

bsquared · 2021-04-07, 17:45

Windows build:

with -psearch avg -threads 8

Code:

nfs: best score is currently 1.266e-08
nfs: found poly better than avg quality
elapsed time: 27.0977 seconds (1221 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 1.040000e-08, new best line = 2
new best score = 1.074000e-08, new best line = 6
new best score = 1.167000e-08, new best line = 11
new best score = 1.229000e-08, new best line = 18
new best score = 1.266000e-08, new best line = 61
nfs: creating ggnfs job parameters for input of size 100
best poly:
# norm 1.329616e-13 alpha -4.762021 e 1.266e-08 rroots 2
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 518246.93
c0: 84865267905977794683633125
c1: -1981237361723192340991
c2: -2697204802913816
c3: 5458443142
c4: 12180
Y0: -578836284879405326839926
Y1: 13343770334947

with -psearch fast -threads 8

Code:

elapsed time: 156.7667 seconds (152 second deadline); poly select done
searching for best poly...
new best score = 9.970000e-09, new best line = 1
new best score = 1.040000e-08, new best line = 2
new best score = 1.074000e-08, new best line = 6
new best score = 1.167000e-08, new best line = 11
new best score = 1.229000e-08, new best line = 18
new best score = 1.266000e-08, new best line = 61
new best score = 1.428000e-08, new best line = 136
nfs: creating ggnfs job parameters for input of size 100
best poly:
# norm 1.695913e-13 alpha -5.449176 e 1.428e-08 rroots 0
n: 1367334477485823565093737451423720863788304129290026132972003205143914928887277670302322035345002167
skew: 460542.12
c0: 264364209926768035382073459
c1: 789976835377316218189
c2: -3043500066840224
c3: -5903074724
c4: 18480
Y0: -521548409549556316408492
Y1: 21442439626079

So, nothing amiss here. I am seeing this message:
"deadline: 638 CPU-seconds per coefficient"

So, I apparently haven't updated to the msieve version that makes this value huge. Although it isn't spending even close to 638 seconds per coefficient, so that may not be the problem.

I think more info is needed from the OP (or anyone else that is having this problem); if you can try to identify where it is getting stuck.

bur · 2021-04-07, 20:33

Quote:

Originally Posted by bsquared

Assuming that's not the problem here, I would recommend using -psearch avg or -psearch good instead of the default poly search. These options stop as soon as an average (good) poly is found rather than using the timing table, which is in need of an update (especially for smaller C100-C110 numbers).

To me this sounds like using these options is a good idea regardless of the problem?

I remember I also saw poly times way above the deadline and wondered why that was the case. I'm running Windows as well. I can't find the exact output in factor.log, but maybe this is similar:

Code:

00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: commencing nfs on c104: 34993011070188327021795022422892723316227257164667460355154317602942007527742978416465823561057801912707
04/02/21 13:00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: commencing poly selection with 4 threads
04/02/21 13:00:03 v1.34.5 @ DESKTOP-L52QKGR, nfs: setting deadline of 417 seconds
04/02/21 13:20:10 v1.34.5 @ DESKTOP-L52QKGR, nfs: completed 4 ranges of size 250 in 1206.4288 seconds
 04/02/21 13:20:10 v1.34.5 @ DESKTOP-L52QKGR, nfs: best poly = # norm 4.345715e-014 alpha -5.924812 e 7.622e-009 rroots 4

The deadline is mostly 300-450 s and the actual time 1200-2600 s.

VBCurtis · 2021-04-08, 00:33

Bur-
The deadline is *per coefficient*, not per search.
1200 sec on poly select with a deadline per-coefficient of 417 seconds is perfectly consistent. The per-coefficient deadline is because there are occasionally specific first-coeff values that "get stuck" in poly select, so the deadline cuts off that particular search to proceed to the next one.

That deadline could be set quite a bit lower for small inputs (like under 120 digits), but for bigger jobs it does its job.

charybdis · 2021-04-08, 02:13

Quote:

Originally Posted by VBCurtis

Bur-
The deadline is *per coefficient*, not per search.
1200 sec on poly select with a deadline per-coefficient of 417 seconds is perfectly consistent. The per-coefficient deadline is because there are occasionally specific first-coeff values that "get stuck" in poly select, so the deadline cuts off that particular search to proceed to the next one.

That deadline could be set quite a bit lower for small inputs (like under 120 digits), but for bigger jobs it does its job.

Actually 417 seconds is yafu's deadline for the whole search, which it prints to factor.log. This is different from the per-coefficient deadline, which only gets printed to the terminal as

Code:

deadline: 8640000 CPU-seconds per coefficient

_____

I don't think this is a Windows vs Linux issue; it's probably related to changes that have been made to msieve. I had a look back at some old logs and it seems the precompiled v1.34.5 Windows binary regularly overshot the deadline:

Code:

09/27/19 21:34:31 v1.34.5 @ scylla, nfs: commencing nfs on c99: 427342969728593249995852717142458734662938233797399924260645630851457103421951613776831171963394999
09/27/19 21:34:32 v1.34.5 @ scylla, nfs: commencing poly selection with 4 threads
09/27/19 21:34:32 v1.34.5 @ scylla, nfs: setting deadline of 289 seconds
09/27/19 21:49:41 v1.34.5 @ scylla, nfs: completed 4 ranges of size 250 in 909.3937 seconds

Clearly some coefficients were taking far too long: only one range was completed per thread. This issue only appeared with degree 4 poly selection, which would explain why Kvasir is seeing it only below 110 digits.

A mingw64 build of v1.35-beta (yafu r379 + msieve r1030) was more reasonable:

Code:

10/19/19 15:51:20 v1.35-beta @ scylla, nfs: commencing nfs on c99: 295246846667425141512796091316580174394940879595078179964227521694311641573564329291532389013361191
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: commencing poly selection with 4 threads
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: setting deadline of 289 seconds
10/19/19 15:51:20 v1.35-beta @ scylla, nfs: expecting degree 4 poly E from 1.33e-008 to > 1.52e-008
10/19/19 15:56:08 v1.35-beta @ scylla, nfs: completed 725 ranges of size 60 in 287.7674 seconds

I had set pbatch=60 to make the ranges smaller, but this would have been okay with the default of 250 too.

However, the search-range per coefficient seems to be much larger for degree 5, so the effect of the 8640000-second deadline is that there isn't time to search many ranges before yafu's whole-search deadline is reached. A single coefficient that takes a long time can still delay the search; this is likely to be a bigger problem on machines with lots of threads.

(this log is from a linux machine but that should be irrelevant)

Code:

05/03/20 09:10:01 v1.35-beta @ selenium, nfs: commencing nfs on c111: 752001002037101772932306843847522458195579123341389985942355224754269877604320469822501875579464492175993551297
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: commencing poly selection with 6 threads
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: setting deadline of 733 seconds
05/03/20 09:10:01 v1.35-beta @ selenium, nfs: expecting degree 5 poly E from 7.56e-10 to > 8.70e-10
05/03/20 09:29:13 v1.35-beta @ selenium, nfs: completed 24 ranges of size 60 in 1151.6684 seconds

This would likely have been worse with the default pbatch=250.

Msieve r1023, which I linked to a few posts back, had lots of changes to the polyselect parameters, so maybe it fixed the issue that Kvasir is seeing with degree 4 numbers, while creating a smaller problem for degree 5 ones. Making pbatch smaller and/or using -psearch avg or fast would seem to be the best workaround.

Perhaps it's time to put a new precompiled Windows binary on sourceforge? The current one is 8 years old.

VBCurtis · 2021-04-08, 03:14

My apologies for the misinformation- I've only used msieve directly, not YAFU, for poly select, so I quoted how msieve works. Mea culpa, and thanks for the correction.

Kvasir · 2021-04-08, 08:12

Is the -psearch parameter available when I call YAFU from aliqueit? Can it be set up in aliquiet.ini or yafu.ini or something?

charybdis · 2021-04-08, 11:26

You can set new defaults for yafu command line options in yafu.ini: just add "psearch=avg" or "psearch=fast".

2021-04-06, 16:52	#1
Kvasir Dec 2020 2⁴ Posts	Bad poly select estimates When I'm running YAFU and it switches to nfs mode after ECM, it has a habit of producing very optimistic estimates (or very bad performance) for number in the low 100's (100-110 digits or so). The following is an example of poly selection for a C100: elapsed time of 3861.2958 seconds exceeds 128 second deadline; poly select done. Why is this? On higher number the estimate is more correct, and the poly selection is often faster.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Poly select and planning for 2,2330M	VBCurtis	Cunningham Tables	70	2021-02-16 06:32
Poly select and planning for 2,2210M	swellman	Cunningham Tables	51	2020-03-22 22:09
YAFU Poly Select Deadline	amphoria	YAFU	22	2016-09-17 09:47
msieve poly select: choosing Stage1norm	VBCurtis	Msieve	0	2016-04-11 21:33
Starting NFS skipping poly select	jux	YAFU	5	2016-01-02 01:01

2021-04-07, 16:26	#3
charybdis Apr 2020 2·5·23 Posts	I think this revision to msieve may be partly responsible? Particularly "deadline_per_coeff = 8640000", which essentially means each leading coefficient is search-range-limited rather than time-limited, so yafu poly selection continues until each thread is done with its first coefficient which could take much longer than the deadline.

2021-04-08, 00:33	#7
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²×7×13² Posts	Bur- The deadline is per coefficient, not per search. 1200 sec on poly select with a deadline per-coefficient of 417 seconds is perfectly consistent. The per-coefficient deadline is because there are occasionally specific first-coeff values that "get stuck" in poly select, so the deadline cuts off that particular search to proceed to the next one. That deadline could be set quite a bit lower for small inputs (like under 120 digits), but for bigger jobs it does its job.

2021-04-08, 03:14	#9
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²×7×13² Posts	My apologies for the misinformation- I've only used msieve directly, not YAFU, for poly select, so I quoted how msieve works. Mea culpa, and thanks for the correction.

2021-04-08, 08:12	#10
Kvasir Dec 2020 2⁴ Posts	Is the -psearch parameter available when I call YAFU from aliqueit? Can it be set up in aliquiet.ini or yafu.ini or something?

2021-04-08, 11:26	#11
charybdis Apr 2020 2×5×23 Posts	You can set new defaults for yafu command line options in yafu.ini: just add "psearch=avg" or "psearch=fast".