mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2016-07-29, 20:29   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

645410 Posts
Default "error: unexpected dense ideal found"

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

Code:
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 is offline   Reply With Quote
Old 2016-07-29, 22:53   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×7×461 Posts
Default

"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.

Code:
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

Last fiddled with by fivemack on 2016-07-29 at 22:55
fivemack is offline   Reply With Quote
Old 2016-07-31, 01:04   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

355510 Posts
Default

Never seen a problem in this neighborhood before. Basically a relation has an ideal below 100 that doesn't appear in the factor base.
jasonp is offline   Reply With Quote
Old 2016-08-07, 13:46   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

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

Code:
-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?
fivemack is offline   Reply With Quote
Old 2016-08-07, 14:40   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32·5·79 Posts
Default

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?
jasonp is offline   Reply With Quote
Old 2016-08-08, 06:07   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·7·461 Posts
Default

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

Code:
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.
fivemack is offline   Reply With Quote
Old 2016-08-08, 14:58   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

355510 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2016-08-08, 17:05   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

266168 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Quote:
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.
xilman is offline   Reply With Quote
Old 2016-08-08, 21:55   #9
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11001001101102 Posts
Default

Quote:
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 ...)

Code:
(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.

Last fiddled with by fivemack on 2016-08-08 at 22:59
fivemack is offline   Reply With Quote
Old 2016-08-08, 23:38   #10
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

160658 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
Dubslow is offline   Reply With Quote
Old 2016-08-09, 19:32   #11
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.

Last fiddled with by jasonp on 2016-08-09 at 19:35
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"lanczos error: only trivial dependencies found" with massive oversieving eigma Msieve 21 2015-05-28 03:27
"error (line 734): unexpected error" fivemack Msieve 0 2014-09-14 08:37
"ERROR: Unable to open spool file." no1hasdisid Software 1 2013-05-06 05:24
mfaktX result: "found 1 factor for M" swl551 GPU Computing 2 2012-12-20 15:20
Would Minimizing "iterations between results file" may reveal "is not prime" earlier? nitai1999 Software 7 2004-08-26 18:12

All times are UTC. The time now is 23:37.


Mon Feb 6 23:37:16 UTC 2023 up 172 days, 21:05, 1 user, load averages: 0.87, 1.03, 1.08

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”