"error: unexpected dense ideal found"

[fivemack]

On two attempts when I've tried to process C250_146_80, I get this message

commencing linear algebra
read 11969669 cycles
cycles contain 39115759 unique relations
read 39115759 relations
using 20 quadratic characters above 4294917296
building initial matrix
error: unexpected dense ideal found

Any idea how to proceed? My current plan is to do manual duplicate elimination and throw away some of the large primes and see if that works better, but that's got no motivation beyond superstition.

[fivemack]

"run svn update more than once every thirty months" seems likely to be a sensible place to start

I'd have expected sort -u on a 60GB file stored on NVMe SSD to take less than four hours.

grep "[0-9]*,[0-9]*:[0-9a-fA-F,]*:[0-9a-fA-F,]*" msieve.dat | sort -u -t: -k1 -T . | tee msieve.dat.u | wc -l

[jasonp]

Never seen a problem in this neighborhood before. Basically a relation has an ideal below 100 that doesn't appear in the factor base.

[fivemack]

svn 993 still shows the problem. I've deduplicated the input file and removed two relations which had a few hundred zero bytes in the middle of the line, and am trying again; I wonder if

-38236219,1450370:23a12b0f,d1c8219d,3ad5,8~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1736033,521561:1a03,1391,3bf4229,e9abb9,8a650f,2ea3d1,523bb,2c825:38671d35,dc65ae9d,195acf9,88d35

(where ~ is a zero byte) might have made the matrix-build step try to look up '8' as a dense relation?

[jasonp]

There wouldn't be a comma or ':' after the 8, so I would assume the relation was rejected.

Would it make sense to instrument the relation whose text caused the error?

[fivemack]

Adding a few obvious printfs, I am even more confused now:

error: unexpected dense ideal found: 
prime 0, address 0x7ffdf212e4c0, p_lo 0 p_hi 0 r_lo 1  r_hi 0
Cycle number 69798
c=0x7f20981ee4d0 c->weight=0 c->cycle.num_relations=1

Obviously the pointer values are irrelevant here, but the zero-value prime and zero-weight cycle are not what I was expecting.

This doesn't seem to be a fragile bug, it's happening however I manipulate the dataset, but it might be awkward for you to download the 35GB data locally. There is a slight peculiarity about the polynomial here, which is that c6 and c0 are not only both squares but also both divisible by 4.

[jasonp]

If it's a side effect of malformed relation text we could try to work backwards to the savefile line that causes it. In that neighborhood of code, variable 'c' is an la_col_t structure defined in include/common.h:281; the 'cycle' field of that structure gives the indexes into the list of relation_t structures given by 'rlist'. relation_t is defined in gnfs/gnfs.h:326, the most useful information there will be the relation 'a' value which can pinpoint the savefile line that's involved. The list of factors in a relation_t structure is runlength-encoded to save space, and it's possible the decompression messes up.

If you have the .mat file then you can skip the very slow matrix build phase with 'skip_matbuild=1' in the NFS command-line arguments, to go straight to reading the matrix in from disk.

[xilman]

Originally Posted by fivemack

This doesn't seem to be a fragile bug, it's happening however I manipulate the dataset, but it might be awkward for you to download the 35GB data locally.

Never underestimate the bandwidth of a panel truck full of mag-tapes.

Or of a small package sent airmail. 35G / week equates to just under half a megabit per second. RDS and Wacky have each transferred many gigabytes of NFS relations over the Atlantic to me for post-processing. They used CD and DVD, but a USB stick might be more appropriate these days.

[fivemack]

If you have the .mat file then you can skip the very slow matrix build phase with 'skip_matbuild=1' in the NFS command-line arguments, to go straight to reading the matrix in from disk.

The error happens about 3MB into the production of the .mat file. Fortunately it's short enough after the start of the -nc2 phase that it's not stupidly slow to run under gdb (though would have taken a quarter as long if I'd remembered to set the breakpoint before running, to compile with debug, to set the breakpoint on the right line ...)

(gdb) print c
$1 = (la_col_t *) 0x7fffdff004d0
(gdb) print *c
$2 = {data = 0x0, weight = 0, cycle = {num_relations = 1, list = 0x8ddac0}}
(gdb) print c->cycle
$3 = {num_relations = 1, list = 0x8ddac0}
(gdb) print c->cycle.list
$4 = (uint32 *) 0x8ddac0
(gdb) print *(c->cycle.list)
$5 = 5666740
(gdb) print rlist[5666740]
$6 = {a = 13511, b = 8949, rel_index = 988992, num_factors_r = 9 '\t', 
  num_factors_a = 8 '\b', 
  factors = 0x3bc766f0 "\t\216+}{\204\065,P\204\071o,\204%X\030\202u}\220\005K\211-q\201\202A'b\206m#\252ir\034\217\202\215\251\331", <incomplete sequence \341>}
(gdb) x/24x rlist[5666740].factors
0x3bc766f0:	0x7d2b8e09	0x2c35847b	0x6f398450	0x5825842c
0x3bc76700:	0x7d758218	0x894b0590	0x8281712d	0x86622741
0x3bc76710:	0x69aa236d	0x828f1c72	0xe1d9a98d	0x00000000
0x3bc76720:	0x00000000	0x00000000	0x00000051	0x00000000
0x3bc76730:	0x946fb037	0x5a6b921d	0x50458a27	0x791f8334
0x3bc76740:	0x1e2d8252	0x810c1382	0x09d98582	0x79870b81

butternut@butternut:/scratch/C250_146_80$ grep "^13511," msieve.dat
13511,10301208:503bb4c1,3234c4f3,af1,92ed87b,216cc5,3e1ef:24a244b9,1eadc45,c2551d,39a7a5,2327ed,13649
13511,8949:709,9EFEAB,941635,8B37B9,462C25,43EF5,26585,78AD:D893C1,A91ED,1E73969
13511,91882855:ac1ad489,6c7954d,6640813,a8faff,511405,4b911,d711:2b1003bd,b5e135d,335fea9,274bb95,10b02e9,8fe25,4f6d

? f(x,y)=21316*y^6+100*x^6
? g(x,y)=9444732965739290427392000000000000000000000000*y+13695791164569918553628942336*x
? factor(f(13511,8949))
%10 = 
[2 3]
[13 1]
[41 1]
[89 1]
[97 1]
[692717 1]    0xA91ED
[14193601 1]  0xD893C1
[31930729 1]  0x1E73969

? factor(g(13511,8949))
%11 = 
[2 13]
[1801 1]  0x709
[30893 1]  0x78AD
[157061 1]  0x26585
[278261 1]  0x43EF5
[4598821 1]  0x462C25
[9123769 1]  0x8B37B9
[9705013 1]  0x941635
[10419883 1]  0x9EFEAB

So the line looks really quite unexceptionable - maybe it's significant that the factors are all 25 bits or less?

Hope this is useful.

Proceeding in a try-things-and-see-what-happens way, I've deleted the lines with a=13511 from msieve.dat, revised the msieve.fb to remove the common factors from A0 and A6 and from R0 and R1, and am rerunning overnight.

[Dubslow]

Originally Posted by fivemack

Proceeding in a try-things-and-see-what-happens way, I've deleted the lines with a=13511 from msieve.dat, revised the msieve.fb to remove the common factors from A0 and A6 and from R0 and R1, and am rerunning overnight.

Wouldn't it be more informative to do these things one at a time? Of course it might be prohibitively untimely.

[jasonp]

Originally Posted by fivemack

There is a slight peculiarity about the polynomial here, which is that c6 and c0 are not only both squares but also both divisible by 4.

The relation you quote looks fine, and upon reflection I think the above is the problem. If the algebraic polynomial mod 2 is zero then 2 is removed from the factor base, hence the complaint about the extra factors.

Any factors of relations that are less than 100 are completely ignored by the filtering, which explains why you had to get to the LA to see anything wrong.