Too many relsets.

[xilman]

I'm playing with msieve again for the first time in years. First thing was to "svn update" and make a cuda-free binary. Second to get the ggnfs siever working again.

Trying it out with a c81 sieves fine but the filtering always crashes with

Found 1821779 relations, need at least 1815330 to proceed.
=> "/home/pcl/nums/MSGG/msieve" -s foo.dat -l ggnfs.log -i foo.ini -v -nf foo.fb -t 12 -nc1


Msieve v. 1.54 (SVN 1043M)
Thu Aug 12 18:05:22 2021
random seeds: 61db686a 3572786c
factoring 140450553265837532472999838666171476981750087734750429689611671345898475942852981 (81 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (81-digit input)
R0: -2188878986130343284
R1: 1
A0: 457229499817116111001
A1: -40079160109703337
A2: -594496820208949
A3: 14596054413
A4: 6118380
skew 1379.25, size 1.639e-11, alpha -4.079, combined = 9.379e-08 rroots = 4

commencing relation filtering
estimated available RAM is 7791.3 MB
commencing duplicate removal, pass 1
found 171067 hash collisions in 1821778 relations
added 42898 free relations
commencing duplicate removal, pass 2
found 182270 duplicates and 1682406 unique relations
memory use: 8.2 MB
reading ideals above 30000
commencing singleton removal, initial pass
memory use: 43.1 MB
reading all ideals from disk
memory use: 49.7 MB
keeping 1386562 ideals with weight <= 200, target excess is 10516
commencing in-memory singleton removal
begin with 1682406 relations and 1386562 unique ideals
reduce to 962376 relations and 553677 ideals in 9 passes
max relations containing the same ideal: 138
removing 422003 relations and 243200 ideals in 178803 cliques
checking relations array at location 1
commencing in-memory singleton removal
begin with 540373 relations and 553677 unique ideals
reduce to 521434 relations and 289478 ideals in 5 passes
max relations containing the same ideal: 95
removing 104985 relations and 55524 ideals in 49461 cliques
checking relations array at location 1
commencing in-memory singleton removal
begin with 416449 relations and 289478 unique ideals
reduce to 414136 relations and 231542 ideals in 4 passes
max relations containing the same ideal: 79
removing 37789 relations and 19403 ideals in 18386 cliques
checking relations array at location 1
commencing in-memory singleton removal
begin with 376347 relations and 231542 unique ideals
reduce to 375950 relations and 211732 ideals in 3 passes
max relations containing the same ideal: 74
relations with 0 large ideals: 184
relations with 1 large ideals: 639
relations with 2 large ideals: 7615
relations with 3 large ideals: 36420
relations with 4 large ideals: 86182
relations with 5 large ideals: 114587
relations with 6 large ideals: 84108
relations with 7+ large ideals: 46215
commencing 2-way merge
reduce to 367891 relation sets and 203673 unique ideals
commencing full merge
error: number of relsets too large
Return value 65280. Terminating...

or similar.

Any ideas what may be going wrong?

Thanks,
Paul

[xilman]

Experimenting by pruning foo.dat ever more severely eventually resulted in a complete factorization.

Perhaps my toy example was just too small for the Perl script to cope with.

[xilman]

Originally Posted by xilman

Experimenting by pruning foo.dat ever more severely eventually resulted in a complete factorization.

Perhaps my toy example was just too small for the Perl script to cope with.

That must have been the problem. A c100 with a polynomial found by cado-nfs ran without problems.

Incidentally, I had to reverse all the signs of the algebraic coefficients because msieve threw up at the concept of factoring a negative integer. Very strange IMO.

Only doing this because cado-nfs is very memory hungry in the linear algebra phase.

[frmky]

Originally Posted by xilman

Experimenting by pruning foo.dat ever more severely eventually resulted in a complete factorization.

Perhaps my toy example was just too small for the Perl script to cope with.

msieve filtering has the option filter_maxrels=X to limit the filtering to using the first X relations in the data file without editing the file because it does struggle with a huge excess of relations.

I agree about the issue with the negative integer. The square root doesn't like it, but that should be easy to check for and fix rather than giving up. I'll look into it.

Edit: Addressed it in my fork at https://github.com/gchilders/msieve_nfsathome. Use the msieve-lacuda-nfsathome branch. Despite the name it compiles and runs fine without CUDA.