Polynomial Selection Parameters Discussion

[Dylan14]

A lower exp_E is (generally) better. So it pushes out polys with a higher exp_E (or in earlier commits, the lognorm, which seems related but I’m not sure).

[EdH]

Originally Posted by Dylan14

A lower exp_E is (generally) better. So it pushes out polys with a higher exp_E (or in earlier commits, the lognorm, which seems related but I’m not sure).

Thanks! Some other things make more sense now, as well.

[swellman]

What is the current thinking on the ropteffort parameter? There is a wide range of values used throughout the Improved params files for CADO thread, including some files which are missing it entirely.

[VBCurtis]

At really low sizes, say under 115 digits, setting ropteffort higher doesn't have any effect- seems there isn't anything left to expend effort on. Also, trials are fast, so anyone can test themselves on e.g. 0.8 vs 1 vs 1.5 etc.

At high sizes, the time spent in root-opt is so small relative to the time spent on size-opt that I've been setting this quite high- like 30+. Again, at some point a higher setting doesn't produce any more effort, so I don't think it matters whether one sets this to 35 or 60.

It's the 115ish to 150ish area where I don't have a good answer; I played with it years ago, and ran into trials where higher settings cost more time but didn't produce any changes in polys. An open question?

[swellman]

Originally Posted by VBCurtis

At really low sizes, say under 115 digits, setting ropteffort higher doesn't have any effect- seems there isn't anything left to expend effort on. Also, trials are fast, so anyone can test themselves on e.g. 0.8 vs 1 vs 1.5 etc.

At high sizes, the time spent in root-opt is so small relative to the time spent on size-opt that I've been setting this quite high- like 30+. Again, at some point a higher setting doesn't produce any more effort, so I don't think it matters whether one sets this to 35 or 60.

It's the 115ish to 150ish area where I don't have a good answer; I played with it years ago, and ran into trials where higher settings cost more time but didn't produce any changes in polys. An open question?

Thank you for summarizing the issue so well. I’m varying ropteffort and nrkeep with the c204 poly search just to get a feel for the resulting poly score and runtime.

[EdH]

I have been trying to study the randomness of "good" polynomials across a search region. I've even graphed exp_E values for a given region/parmeters. I'm sure someone's already explored this. Is there any documentation that I might be capable of understanding available on this?

Is there a way to backtrack a polynomial to any of its search criteria?


Edit: Extra question: How large is too large for admax?

[jasonp]

The limit on admax is 1/(poly_degree+1) the size of the number to be factored. That's the extreme upper limit; Kleinjung's 2006 paper gives more sensible bounds on admax based on the largest and smallest skew that you can tolerate. The optimal skew goes down as a_d increases, taking the search space for the root optimization with it.

[EdH]

Originally Posted by EdH

I have been trying to study the randomness of "good" polynomials across a search region. I've even graphed exp_E values for a given region/parmeters. I'm sure someone's already explored this. Is there any documentation that I might be capable of understanding available on this?
. . .

I reran the range from 130M-132M at P=16M because P=2M found a cownoise MurphyE score of 2.203 for 130M-133M. The rerun only covered 130M-132M and only 130M to the below number was graphed. The cownoise MurphyE for the rerun was only 2.109. However, I don't know if the original best may have been within the last third of the original run. I may yet run that range to determine if anything better shows itself.

Here are some graphs of exp_E for a CADO-NFS run with the following parameters:

admin-admax: 130000000-131756940
incr: 210
P: 16000000
adrange: 1680
sopteffort: 1

Parameters not listed above were set to the default values in the CADO-NFS params.c200 file.

All of the below points represent the smallest raw exp_E score for a given search value. The first graph is of the entire set. The second is of the lowest value. The third is of the fifth lowest value, since CADO-NFS said the 4-th poly (starting at 0) after size optimization was chosen.

Edit: Rerunning the final third of the range (132M-133M) at P=16M netted only a MurphyE of 2.078 per cownoise. The new range is not reflected in the graphs.

[swellman]

Here is some data I have gathered, really started as a personal education on the effects of certain parameters on CADO performance. Nothing new here, but it does provide some actual results with respect to speed and the polys produced.

P (M)	admin (M)	admax (M)	adrange (M)	incr	nq	nrkeep	ropteffort	Size-opt time (wall clock minutes)	Root-opt time (wall clock minutes)	Total Time (wall clock minutes)	Best poly score (cownoise)	Best poly in n-th place after size opt				
4	60	61	60060	30030	15625	50	35	110	175	285	1.44E-15	4				
4	60	61	60060	30030	15625	200	35	110	675	785	1.45E-15	4				
4	60	61	60060	30030	15625	50	10	110	90	200	1.44E-15	4				
4	60	61	60060	30030	15625	200	10	110	330	440	1.44E-15	4				
8	60	61	60060	30030	15625	50	35	215	180	395	1.88E-15	0				
8	60	61	60060	30030	15625	200	35	215	620	835	1.88E-15	0				
8	60	61	60060	30030	15625	50	10	220	100	320	1.88E-15	0				
8	60	61	60060	30030	15625	200	10	220	335	555	1.88E-15	0				
14	60	61	60060	30030	15625	50	35	370	175	545	1.72E-15	0				
14	60	61	60060	30030	15625	200	35	365	670	        1.72E-15	0				
14	60	61	60060	30030	15625	50	10	485	85	570	1.66E-15	0				
14	60	61	60060	30030	15625	200	10	365	330	695	1.66E-15	0

All data was measured with -t 4 on a fully tasked i7-7705 with 32 Gb installed.

sopteffort was default (zero) in all cases. I chose these parameters for speed of testing, not optimizing a poly search. adrange and incr are too large for a 60-61M search. But the timings should be good.

Got another run grinding away on the same machine with incr = 9240 and nq = 4620. Much slower but the parameters are more realistic.