20180426, 16:02  #1 
"Ed Hall"
Dec 2009
Adirondack Mtns
7202_{8} Posts 
"too few cycles, matrix probably cannot build"
I'm running several instances of a variant of yoyo's yafu.pl and have discovered it's failing regularly on many 100 dd composites. I've started gathering examples. Here are five:
Code:
1574511877475876335316372499005658025399466737139649097909807522789878189373960844795718204018822451 1800564888014950938521459017065544154608289307498073557047579694832535418806830055691078264692681971 1799069283919885736773557773320655283053593370861452162980412937307504604322920717391232110473296877 1941652481212430800771664311330077572073638734507074252601030360303069469052917861590445467265513617 1600108174771308311440054791086668943407407343625259307020396274538801026760430257008769115560700427 Code:
Thu Apr 26 11:18:34 2018 Thu Apr 26 11:18:34 2018 commencing relation filtering Thu Apr 26 11:18:34 2018 estimated available RAM is 7867.5 MB Thu Apr 26 11:18:34 2018 commencing duplicate removal, pass 1 Thu Apr 26 11:19:06 2018 found 408823 hash collisions in 4600431 relations Thu Apr 26 11:19:10 2018 added 155071 free relations Thu Apr 26 11:19:10 2018 commencing duplicate removal, pass 2 Thu Apr 26 11:19:11 2018 found 159049 duplicates and 4596453 unique relations Thu Apr 26 11:19:11 2018 memory use: 19.6 MB Thu Apr 26 11:19:11 2018 reading ideals above 100000 Thu Apr 26 11:19:11 2018 commencing singleton removal, initial pass Thu Apr 26 11:19:40 2018 memory use: 172.2 MB Thu Apr 26 11:19:40 2018 reading all ideals from disk Thu Apr 26 11:19:40 2018 memory use: 142.6 MB Thu Apr 26 11:19:40 2018 keeping 5297083 ideals with weight <= 200, target excess is 41917 Thu Apr 26 11:19:40 2018 commencing inmemory singleton removal Thu Apr 26 11:19:40 2018 begin with 4596453 relations and 5297083 unique ideals Thu Apr 26 11:19:42 2018 reduce to 1321099 relations and 1271455 ideals in 21 passes Thu Apr 26 11:19:42 2018 max relations containing the same ideal: 83 Thu Apr 26 11:19:42 2018 relations with 0 large ideals: 593 Thu Apr 26 11:19:42 2018 relations with 1 large ideals: 5128 Thu Apr 26 11:19:42 2018 relations with 2 large ideals: 34697 Thu Apr 26 11:19:42 2018 relations with 3 large ideals: 144841 Thu Apr 26 11:19:42 2018 relations with 4 large ideals: 331827 Thu Apr 26 11:19:42 2018 relations with 5 large ideals: 425278 Thu Apr 26 11:19:42 2018 relations with 6 large ideals: 270876 Thu Apr 26 11:19:42 2018 relations with 7+ large ideals: 107859 Thu Apr 26 11:19:42 2018 commencing 2way merge Thu Apr 26 11:19:43 2018 reduce to 698957 relation sets and 649742 unique ideals Thu Apr 26 11:19:43 2018 ignored 429 oversize relation sets Thu Apr 26 11:19:43 2018 commencing full merge Thu Apr 26 11:19:51 2018 memory use: 33.7 MB Thu Apr 26 11:19:51 2018 found 70082 cycles, need 163940 Thu Apr 26 11:19:51 2018 too few cycles, matrix probably cannot build Code:
... nfs: commencing algebraic side lattice sieving over range: 1160000  1162500 nfs: commencing algebraic side lattice sieving over range: 1162500  1165000 nfs: commencing algebraic side lattice sieving over range: 1177500  1180000 nfs: commencing algebraic side lattice sieving over range: 1165000  1167500 nfs: commencing algebraic side lattice sieving over range: 1167500  1170000 nfs: commencing algebraic side lattice sieving over range: 1172500  1175000 nfs: commencing algebraic side lattice sieving over range: 1170000  1172500 nfs: commencing algebraic side lattice sieving over range: 1175000  1177500 total yield: 39005, q=1177507 (0.00138 sec/rel) total yield: 41529, q=1175003 (0.00138 sec/rel) total yield: 41540, q=1172503 (0.00138 sec/rel) total yield: 42503, q=1162501 (0.00138 sec/rel) total yield: 44463, q=1167539 (0.00133 sec/rel) total yield: 45453, q=1170007 (0.00135 sec/rel) total yield: 46028, q=1165001 (0.00133 sec/rel) total yield: 47561, q=1180009 (0.00133 sec/rel) nfs: commencing msieve filtering 1800564888014950938521459017065544154608289307498073557047579694832535418806830055691078264692681971 ~/Math/yafu$ Code:
... nfs: commencing algebraic side lattice sieving over range: 1167500  1170000 nfs: commencing msieve filtering 1600108174771308311440054791086668943407407343625259307020396274538801026760430257008769115560700427 Error, no result found Here's the YAFU header info from one of the machines: Code:
04/26/18 11:51:19 v1.35beta @ math94, System/Build Info: Using GMPECM 7.0.4, Powered by GMP 6.1.2 detected Intel(R) Core(TM) i72600 CPU @ 3.40GHz detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes measured cpu frequency ~= 3392.244760 using 1 random witnesses for RabinMiller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 Code:
./yafu "factor(<number>)" Thanks for any help. 
20180426, 17:32  #2 
"Curtis"
Feb 2005
Riverside, CA
11253_{8} Posts 
The script is supposed to interpret that msieve outcome as "we need another round of sieving". I don't use the perl script, but in the python script I can edit the number of relations needed to attempt filtering; if you adjust that upward by 20% or so the error should disappear (or be 5% as common).
Of course, that avoids the problem rather than cures it, as there's a bug preventing a resumption of sieving when a matrix cannot be built. Note that "filtering needs 1000000 more relations" usually means you're not close to building a matrix, while "too few cycles" usually means you're right on the cusp of a usable matrix. That's why I suggest 1520% more relations as a way to avoid the bug. 
20180426, 17:33  #3 
"Ben"
Feb 2007
2×3^{2}×191 Posts 
The joys of working with branch code .
The "matrix probably cannot build" message is printed by the msieve library, just prior to that library calling exit(0). In the prepackaged binaries that I used to provide I removed all of these (yes, there are others for a variety of abnormal conditions) exit calls before linking in the library. If you are building the branch wip version of yafu then your msieve probably still has the exits. That particular one, at least in the msieve code I currently have, occurs on line 627 of merge.c. You'd have to comment out the exit and rebuild msieve, then rebuild yafu. The command line bit is something I'm working on where the yafu shell in linux will recognize backspaces to delete text, and up arrows and down arrows for command browsing. But, if yafu exits abnormally (ctrlc, or exit()), then you get the effect you observed. The temporary fix (I hope, this is untested) would be to: 1) edit line 121 to : #if 0 //defined(__unix__) 2) edit line 355 to: #if 1 //!defined(__unix__) 3) edit line 337 to: #if 0 //defined(__unix__) Sorry! Thanks for the feedback! 
20180426, 17:52  #4 
"Ed Hall"
Dec 2009
Adirondack Mtns
2·3·619 Posts 
Thanks for all the help from both of you.
I will look into the modifications. I do have a bit of interesting additional info, though. All the failures I referenced were from i7 2600 machines, but I tried a Core2 and it finished properly. There are three differences, (ECM, GMP, CPU): Code:
04/26/18 13:33:11 v1.35beta @ math44, System/Build Info: Using GMPECM 7.0.3, Powered by GMP 6.1.1 detected Intel(R) Core(TM)2 Quad CPU Q8400 @ 2.66GHz detected L1 = 32768 bytes, L2 = 2097152 bytes, CL = 64 bytes measured cpu frequency ~= 2660.013600 using 1 random witnesses for RabinMiller PRP checks =============================================================== ======= Welcome to YAFU (Yet Another Factoring Utility) ======= ======= bbuhrow@gmail.com ======= ======= Type help at any time, or quit to quit ======= =============================================================== cached 78498 primes. pmax = 999983 Code:
... nfs: commencing msieve filtering 1600108174771308311440054791086668943407407343625259307020396274538801026760430257008769115560700427 nfs: commencing algebraic side lattice sieving over range: 1190000  1200000 nfs: commencing algebraic side lattice sieving over range: 1180000  1190000 total yield: 167185, q=1200007 (0.00134 sec/rel) total yield: 173738, q=1190011 (0.00133 sec/rel) nfs: commencing msieve filtering 1600108174771308311440054791086668943407407343625259307020396274538801026760430257008769115560700427 nfs: commencing msieve linear algebra linear algebra completed 238825 of 240167 dimensions (99.4%, ETA 0h 0m) nfs: commencing msieve sqrt NFS elapsed time = 4628.5065 seconds. Total factoring time = 5027.3603 seconds ***factors found*** P50 = 44073246161242488859802237851252243217008990661099 P50 = 36305657380382052089741809788137222014836299339873 1 
20180426, 18:25  #5 
"Ben"
Feb 2007
2·3^{2}·191 Posts 
A thought, RE: different outcomes on different machines, is that with different thread counts, the job may proceed through different ranges of q. Since the error is related to matrices "on the cusp" of being created, small difference in ranges of q is all that may be needed to have one work and another fail.

20180426, 19:04  #6  
Sep 2009
2·1,021 Posts 
Quote:
If that fails "stty sane" might fix it. Chris 

20180426, 21:04  #7 
Tribal Bullet
Oct 2004
3^{3}×131 Posts 
The calls to exit() were a holdover from when the library was only used in one application and not the complete factoring frameworks we have now. Getting rid of them is easy but they need to be replaced with actual return paths that e.g. close any open files and propagate error information up. Not having this makes embedding libmsieve within application much harder.

20180426, 22:36  #8 
"Ed Hall"
Dec 2009
Adirondack Mtns
2×3×619 Posts 
Well, commenting out exit(0) didn't solve it.
It just delayed it: Code:
Thu Apr 26 14:31:22 2018 commencing linear algebra Thu Apr 26 14:31:22 2018 read 71308 cycles Thu Apr 26 14:31:22 2018 cycles contain 388962 unique relations Thu Apr 26 14:31:24 2018 read 388962 relations Thu Apr 26 14:31:24 2018 using 20 quadratic characters above 4294917295 Thu Apr 26 14:31:26 2018 building initial matrix Thu Apr 26 14:31:28 2018 memory use: 49.8 MB Thu Apr 26 14:31:28 2018 read 71308 cycles Thu Apr 26 14:31:28 2018 matrix is 161626 x 71308 (34.5 MB) with weight 10709416 (150.19/col) Thu Apr 26 14:31:28 2018 sparse part has weight 8195436 (114.93/col) Thu Apr 26 14:31:29 2018 filtering completed in 2 passes Thu Apr 26 14:31:29 2018 matrix is 148675 x 58795 (29.1 MB) with weight 8958009 (152.36/col) Thu Apr 26 14:31:29 2018 sparse part has weight 6934564 (117.94/col) Thu Apr 26 14:31:29 2018 matrix starts at (0, 0) Thu Apr 26 14:31:29 2018 matrix is 148675 x 58795 (29.1 MB) with weight 8958009 (152.36/col) Thu Apr 26 14:31:29 2018 sparse part has weight 6934564 (117.94/col) Thu Apr 26 14:31:29 2018 matrix needs more columns than rows; try adding 23% more relations Code:
nfs: commencing msieve linear algebra *** Error in `./yafu': free(): invalid next size (normal): 0x0000000002208d50 *** ======= Backtrace: ========= /lib/x86_64linuxgnu/libc.so.6(+0x777e5)[0x7f57bf1a37e5] /lib/x86_64linuxgnu/libc.so.6(+0x8037a)[0x7f57bf1ac37a] /lib/x86_64linuxgnu/libc.so.6(cfree+0x4c)[0x7f57bf1b053c] ./yafu[0x499653] ./yafu[0x491403] ./yafu[0x448113] ./yafu[0x426e18] ./yafu[0x4179d6] ./yafu[0x4195ed] ./yafu[0x4198d8] ./yafu[0x40569d] /lib/x86_64linuxgnu/libc.so.6(__libc_start_main+0xf0)[0x7f57bf14c830] ./yafu[0x406279] ======= Memory map: ======== 0040000000561000 rxp 00000000 08:01 2627508 /home/math94/Math/yafu/yafu 0076000000761000 rxp 00160000 08:01 2627508 /home/math94/Math/yafu/yafu 0076100000771000 rwxp 00161000 08:01 2627508 /home/math94/Math/yafu/yafu 0077100000779000 rwxp 00000000 00:00 0 00d6a0000316f000 rwxp 00000000 00:00 0 [heap] 7f57880000007f5788189000 rwxp 00000000 00:00 0 7f57881890007f578c000000 p 00000000 00:00 0 7f57900000007f579018b000 rwxp 00000000 00:00 0 7f579018b0007f5794000000 p 00000000 00:00 0 7f57980000007f579818d000 rwxp 00000000 00:00 0 7f579818d0007f579c000000 p 00000000 00:00 0 7f57a00000007f57a0189000 rwxp 00000000 00:00 0 7f57a01890007f57a4000000 p 00000000 00:00 0 7f57a40000007f57a418d000 rwxp 00000000 00:00 0 7f57a418d0007f57a8000000 p 00000000 00:00 0 7f57a80000007f57a818b000 rwxp 00000000 00:00 0 7f57a818b0007f57ac000000 p 00000000 00:00 0 7f57b00000007f57b018b000 rwxp 00000000 00:00 0 7f57b018b0007f57b4000000 p 00000000 00:00 0 7f57b77ff0007f57b7800000 p 00000000 00:00 0 7f57b78000007f57b8000000 rwxp 00000000 00:00 0 7f57b80000007f57b8189000 rwxp 00000000 00:00 0 7f57b81890007f57bc000000 p 00000000 00:00 0 7f57bc1260007f57bc127000 p 00000000 00:00 0 7f57bc1270007f57bc927000 rwxp 00000000 00:00 0 7f57bc9270007f57bc928000 p 00000000 00:00 0 7f57bc9280007f57bd128000 rwxp 00000000 00:00 0 7f57be7150007f57be72b000 rxp 00000000 08:01 2888878 /lib/x86_64linuxgnu/libgcc_s.so.1 7f57be72b0007f57be92a000 p 00016000 08:01 2888878 /lib/x86_64linuxgnu/libgcc_s.so.1 7f57be92a0007f57be92b000 rwxp 00015000 08:01 2888878 /lib/x86_64linuxgnu/libgcc_s.so.1 7f57be92b0007f57be92c000 p 00000000 00:00 0 7f57be92c0007f57bf12c000 rwxp 00000000 00:00 0 7f57bf12c0007f57bf2ec000 rxp 00000000 08:01 2888840 /lib/x86_64linuxgnu/libc2.23.so 7f57bf2ec0007f57bf4ec000 p 001c0000 08:01 2888840 /lib/x86_64linuxgnu/libc2.23.so 7f57bf4ec0007f57bf4f0000 rxp 001c0000 08:01 2888840 /lib/x86_64linuxgnu/libc2.23.so 7f57bf4f00007f57bf4f2000 rwxp 001c4000 08:01 2888840 /lib/x86_64linuxgnu/libc2.23.so 7f57bf4f20007f57bf4f6000 rwxp 00000000 00:00 0 7f57bf4f60007f57bf4f9000 rxp 00000000 08:01 2888864 /lib/x86_64linuxgnu/libdl2.23.so 7f57bf4f90007f57bf6f8000 p 00003000 08:01 2888864 /lib/x86_64linuxgnu/libdl2.23.so 7f57bf6f80007f57bf6f9000 rxp 00002000 08:01 2888864 /lib/x86_64linuxgnu/libdl2.23.so 7f57bf6f90007f57bf6fa000 rwxp 00003000 08:01 2888864 /lib/x86_64linuxgnu/libdl2.23.so 7f57bf6fa0007f57bf802000 rxp 00000000 08:01 2888910 /lib/x86_64linuxgnu/libm2.23.so 7f57bf8020007f57bfa01000 p 00108000 08:01 2888910 /lib/x86_64linuxgnu/libm2.23.so 7f57bfa010007f57bfa02000 rxp 00107000 08:01 2888910 /lib/x86_64linuxgnu/libm2.23.so 7f57bfa020007f57bfa03000 rwxp 00108000 08:01 2888910 /lib/x86_64linuxgnu/libm2.23.so 7f57bfa030007f57bfa1b000 rxp 00000000 08:01 2888986 /lib/x86_64linuxgnu/libpthread2.23.so 7f57bfa1b0007f57bfc1a000 p 00018000 08:01 2888986 /lib/x86_64linuxgnu/libpthread2.23.so 7f57bfc1a0007f57bfc1b000 rxp 00017000 08:01 2888986 /lib/x86_64linuxgnu/libpthread2.23.so 7f57bfc1b0007f57bfc1c000 rwxp 00018000 08:01 2888986 /lib/x86_64linuxgnu/libpthread2.23.so 7f57bfc1c0007f57bfc20000 rwxp 00000000 00:00 0 7f57bfc200007f57bfc96000 rxp 00000000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2 7f57bfc960007f57bfe96000 p 00076000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2 7f57bfe960007f57bfe97000 rxp 00076000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2 7f57bfe970007f57bfe98000 rwxp 00077000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2 7f57bfe980007f57bfebe000 rxp 00000000 08:01 2888812 /lib/x86_64linuxgnu/ld2.23.so 7f57bffa30007f57c00a6000 rwxp 00000000 00:00 0 7f57c00bc0007f57c00bd000 rwxp 00000000 00:00 0 7f57c00bd0007f57c00be000 rxp 00025000 08:01 2888812 /lib/x86_64linuxgnu/ld2.23.so 7f57c00be0007f57c00bf000 rwxp 00026000 08:01 2888812 /lib/x86_64linuxgnu/ld2.23.so 7f57c00bf0007f57c00c0000 rwxp 00000000 00:00 0 7ffd4d1d10007ffd4d1f2000 rwxp 00000000 00:00 0 [stack] 7ffd4d1fb0007ffd4d1fe000 rp 00000000 00:00 0 [vvar] 7ffd4d1fe0007ffd4d200000 rxp 00000000 00:00 0 [vdso] ffffffffff600000ffffffffff601000 rxp 00000000 00:00 0 [vsyscall] Aborted (core dumped) I'll try the trunk version for my 8 thread machines? Thanks everyone. 
20180427, 02:42  #9 
"Ed Hall"
Dec 2009
Adirondack Mtns
2×3×619 Posts 
The /trunk svn only made it a little further:
Code:
Thu Apr 26 18:23:22 2018 commencing linear algebra Thu Apr 26 18:23:22 2018 read 71308 cycles Thu Apr 26 18:23:22 2018 cycles contain 388962 unique relations Thu Apr 26 18:23:24 2018 read 388962 relations Thu Apr 26 18:23:24 2018 using 20 quadratic characters above 4294917295 Thu Apr 26 18:23:26 2018 building initial matrix Thu Apr 26 18:23:29 2018 memory use: 49.8 MB Thu Apr 26 18:23:29 2018 read 71308 cycles Thu Apr 26 18:23:29 2018 matrix is 161626 x 71308 (34.5 MB) with weight 10709416 (150.19/col) Thu Apr 26 18:23:29 2018 sparse part has weight 8195436 (114.93/col) Thu Apr 26 18:23:29 2018 filtering completed in 2 passes Thu Apr 26 18:23:29 2018 matrix is 148675 x 58795 (29.1 MB) with weight 8958009 (152.36/col) Thu Apr 26 18:23:29 2018 sparse part has weight 6934564 (117.94/col) Thu Apr 26 18:23:29 2018 matrix starts at (0, 0) Thu Apr 26 18:23:29 2018 matrix is 148675 x 58795 (29.1 MB) with weight 8958009 (152.36/col) Thu Apr 26 18:23:29 2018 sparse part has weight 6934564 (117.94/col) Thu Apr 26 18:23:29 2018 matrix needs more columns than rows; try adding 23% more relations Thu Apr 26 18:23:29 2018 saving the first 48 matrix rows for later Thu Apr 26 18:23:29 2018 matrix includes 64 packed rows Thu Apr 26 18:23:29 2018 matrix is 148627 x 58795 (28.3 MB) with weight 7735194 (131.56/col) Thu Apr 26 18:23:29 2018 sparse part has weight 6835511 (116.26/col) Thu Apr 26 18:23:29 2018 using block size 8192 and superblock size 786432 for processor cache size 8192 kB Thu Apr 26 18:23:30 2018 commencing Lanczos iteration Thu Apr 26 18:23:30 2018 memory use: 21.9 MB Thu Apr 26 18:23:30 2018 lanczos error: submatrix is not invertible Thu Apr 26 18:23:30 2018 lanczos halted after 2 iterations (dim = 63) Code:
04/26/18 22:29:46 v1.34.5 @ math94, System/Build Info: Using GMPECM 7.0.4, Powered by GMP 6.1.2 detected Intel(R) Core(TM) i72600 CPU @ 3.40GHz detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes measured cpu frequency ~= 3392.234920 
20180427, 03:30  #10 
"Ed Hall"
Dec 2009
Adirondack Mtns
2×3×619 Posts 

20180427, 04:31  #11 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3×29×83 Posts 
My simple work around is to just do that little bit more sieving. For instance when aliqueit hangs due to this exit call, the following suffices to fix it:
Code:
^Z num yafusieve fg ^C Code:
alias num='head n 1 nfs.job  cut d " " f 2 > num' alias yafusieve='~/yafu/yafu "nfs($(cat num))" ns' ^Z to pause aliqueit, "manually" get yafu to do the overthehump sieving, then resume aliqueit and cancel the "auto increasing" ECM; it will restart another yafu, which (with R=1) will detect the rels file and restart with filtering, this time succeeding thanks to the extra sieving. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
AouessareEl HaddouchiEssaaidi "test": "if Mp has no factor, it is prime!"  wildrabbitt  Miscellaneous Math  11  20150306 08:17 
Feature request @ "too few cycles" after filtering  Andi47  Msieve  2  20100111 08:50 
Error: "matrix must have more columns than rows"  mdettweiler  Msieve  10  20090317 02:38 
Would Minimizing "iterations between results file" may reveal "is not prime" earlier?  nitai1999  Software  7  20040826 18:12 