mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   YAFU (https://www.mersenneforum.org/forumdisplay.php?f=96)
-   -   "too few cycles, matrix probably cannot build" (https://www.mersenneforum.org/showthread.php?t=23300)

EdH 2018-04-26 16:02

"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]I've traced the trouble down to YAFU failing to create a matrix and simply quitting. Here's the nfs.log from one of the above numbers:
[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 in-memory 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 2-way 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]This is what I see in a terminal running YAFU directly:
[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]This is what I see from the perl script:
[code]
...
nfs: commencing algebraic side lattice sieving over range: 1167500 - 1170000
nfs: commencing msieve filtering
1600108174771308311440054791086668943407407343625259307020396274538801026760430257008769115560700427
Error, no result found
[/code]This has put a big hurdle in my factordb composite work, since my machines continually try to clear these without success.

Here's the YAFU header info from one of the machines:
[code]
04/26/18 11:51:19 v1.35-beta @ math94, System/Build Info:
Using GMP-ECM 7.0.4, Powered by GMP 6.1.2
detected Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.244760
using 1 random witnesses for Rabin-Miller 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]One last observation: When YAFU quits when run via:
[code]
./yafu "factor(<number>)"
[/code]I can no longer type within the terminal that ran YAFU. CTRL+C functions properly, but standard letters and numbers do not appear.

Thanks for any help.

VBCurtis 2018-04-26 17:32

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 15-20% more relations as a way to avoid the bug.

bsquared 2018-04-26 17:33

The joys of working with branch code :smile:.

The "matrix probably cannot build" message is printed by the msieve library, just prior to that library calling exit(0). In the pre-packaged 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 (ctrl-c, 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!

EdH 2018-04-26 17:52

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.35-beta @ math44, System/Build Info:
Using GMP-ECM [B]7.0.3[/B], Powered by GMP [B]6.1.1[/B]
detected Intel(R) Core(TM)2 Quad CPU [B]Q8400[/B] @ 2.66GHz
detected L1 = 32768 bytes, L2 = 2097152 bytes, CL = 64 bytes
measured cpu frequency ~= 2660.013600
using 1 random witnesses for Rabin-Miller 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]The tail end of the run:
[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
[/code]Thanks again. Off to try the changes, as soon as I get through some other of life's delays...

bsquared 2018-04-26 18:25

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.

chris2be8 2018-04-26 19:04

[QUOTE=EdH;486280]One last observation: When YAFU quits when run via:
[code]
./yafu &quot;factor(<number>)&quot;
[/code]I can no longer type within the terminal that ran YAFU. CTRL+C functions properly, but standard letters and numbers do not appear.

Thanks for any help.[/QUOTE]

Try "stty echo" (you will need to type it blind), next time you get into that state.

If that fails "stty sane" might fix it.

Chris

jasonp 2018-04-26 21:04

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.

EdH 2018-04-26 22:36

Well, commenting out exit(0) didn't solve it.:sad:

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 2-3% more relations
[/code]As jasonp referred to, removing the exit(-1) in the "matrix needs more columns" conditional statement had some really "bad" effects:
[code]
nfs: commencing msieve linear algebra
*** Error in `./yafu': free(): invalid next size (normal): 0x0000000002208d50 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f57bf1a37e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7f57bf1ac37a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f57bf1b053c]
./yafu[0x499653]
./yafu[0x491403]
./yafu[0x448113]
./yafu[0x426e18]
./yafu[0x4179d6]
./yafu[0x4195ed]
./yafu[0x4198d8]
./yafu[0x40569d]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f57bf14c830]
./yafu[0x406279]
======= Memory map: ========
00400000-00561000 r-xp 00000000 08:01 2627508 /home/math94/Math/yafu/yafu
00760000-00761000 r-xp 00160000 08:01 2627508 /home/math94/Math/yafu/yafu
00761000-00771000 rwxp 00161000 08:01 2627508 /home/math94/Math/yafu/yafu
00771000-00779000 rwxp 00000000 00:00 0
00d6a000-0316f000 rwxp 00000000 00:00 0 [heap]
7f5788000000-7f5788189000 rwxp 00000000 00:00 0
7f5788189000-7f578c000000 ---p 00000000 00:00 0
7f5790000000-7f579018b000 rwxp 00000000 00:00 0
7f579018b000-7f5794000000 ---p 00000000 00:00 0
7f5798000000-7f579818d000 rwxp 00000000 00:00 0
7f579818d000-7f579c000000 ---p 00000000 00:00 0
7f57a0000000-7f57a0189000 rwxp 00000000 00:00 0
7f57a0189000-7f57a4000000 ---p 00000000 00:00 0
7f57a4000000-7f57a418d000 rwxp 00000000 00:00 0
7f57a418d000-7f57a8000000 ---p 00000000 00:00 0
7f57a8000000-7f57a818b000 rwxp 00000000 00:00 0
7f57a818b000-7f57ac000000 ---p 00000000 00:00 0
7f57b0000000-7f57b018b000 rwxp 00000000 00:00 0
7f57b018b000-7f57b4000000 ---p 00000000 00:00 0
7f57b77ff000-7f57b7800000 ---p 00000000 00:00 0
7f57b7800000-7f57b8000000 rwxp 00000000 00:00 0
7f57b8000000-7f57b8189000 rwxp 00000000 00:00 0
7f57b8189000-7f57bc000000 ---p 00000000 00:00 0
7f57bc126000-7f57bc127000 ---p 00000000 00:00 0
7f57bc127000-7f57bc927000 rwxp 00000000 00:00 0
7f57bc927000-7f57bc928000 ---p 00000000 00:00 0
7f57bc928000-7f57bd128000 rwxp 00000000 00:00 0
7f57be715000-7f57be72b000 r-xp 00000000 08:01 2888878 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f57be72b000-7f57be92a000 ---p 00016000 08:01 2888878 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f57be92a000-7f57be92b000 rwxp 00015000 08:01 2888878 /lib/x86_64-linux-gnu/libgcc_s.so.1
7f57be92b000-7f57be92c000 ---p 00000000 00:00 0
7f57be92c000-7f57bf12c000 rwxp 00000000 00:00 0
7f57bf12c000-7f57bf2ec000 r-xp 00000000 08:01 2888840 /lib/x86_64-linux-gnu/libc-2.23.so
7f57bf2ec000-7f57bf4ec000 ---p 001c0000 08:01 2888840 /lib/x86_64-linux-gnu/libc-2.23.so
7f57bf4ec000-7f57bf4f0000 r-xp 001c0000 08:01 2888840 /lib/x86_64-linux-gnu/libc-2.23.so
7f57bf4f0000-7f57bf4f2000 rwxp 001c4000 08:01 2888840 /lib/x86_64-linux-gnu/libc-2.23.so
7f57bf4f2000-7f57bf4f6000 rwxp 00000000 00:00 0
7f57bf4f6000-7f57bf4f9000 r-xp 00000000 08:01 2888864 /lib/x86_64-linux-gnu/libdl-2.23.so
7f57bf4f9000-7f57bf6f8000 ---p 00003000 08:01 2888864 /lib/x86_64-linux-gnu/libdl-2.23.so
7f57bf6f8000-7f57bf6f9000 r-xp 00002000 08:01 2888864 /lib/x86_64-linux-gnu/libdl-2.23.so
7f57bf6f9000-7f57bf6fa000 rwxp 00003000 08:01 2888864 /lib/x86_64-linux-gnu/libdl-2.23.so
7f57bf6fa000-7f57bf802000 r-xp 00000000 08:01 2888910 /lib/x86_64-linux-gnu/libm-2.23.so
7f57bf802000-7f57bfa01000 ---p 00108000 08:01 2888910 /lib/x86_64-linux-gnu/libm-2.23.so
7f57bfa01000-7f57bfa02000 r-xp 00107000 08:01 2888910 /lib/x86_64-linux-gnu/libm-2.23.so
7f57bfa02000-7f57bfa03000 rwxp 00108000 08:01 2888910 /lib/x86_64-linux-gnu/libm-2.23.so
7f57bfa03000-7f57bfa1b000 r-xp 00000000 08:01 2888986 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f57bfa1b000-7f57bfc1a000 ---p 00018000 08:01 2888986 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f57bfc1a000-7f57bfc1b000 r-xp 00017000 08:01 2888986 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f57bfc1b000-7f57bfc1c000 rwxp 00018000 08:01 2888986 /lib/x86_64-linux-gnu/libpthread-2.23.so
7f57bfc1c000-7f57bfc20000 rwxp 00000000 00:00 0
7f57bfc20000-7f57bfc96000 r-xp 00000000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2
7f57bfc96000-7f57bfe96000 ---p 00076000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2
7f57bfe96000-7f57bfe97000 r-xp 00076000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2
7f57bfe97000-7f57bfe98000 rwxp 00077000 08:01 2635156 /usr/local/lib/libgmp.so.10.3.2
7f57bfe98000-7f57bfebe000 r-xp 00000000 08:01 2888812 /lib/x86_64-linux-gnu/ld-2.23.so
7f57bffa3000-7f57c00a6000 rwxp 00000000 00:00 0
7f57c00bc000-7f57c00bd000 rwxp 00000000 00:00 0
7f57c00bd000-7f57c00be000 r-xp 00025000 08:01 2888812 /lib/x86_64-linux-gnu/ld-2.23.so
7f57c00be000-7f57c00bf000 rwxp 00026000 08:01 2888812 /lib/x86_64-linux-gnu/ld-2.23.so
7f57c00bf000-7f57c00c0000 rwxp 00000000 00:00 0
7ffd4d1d1000-7ffd4d1f2000 rwxp 00000000 00:00 0 [stack]
7ffd4d1fb000-7ffd4d1fe000 r--p 00000000 00:00 0 [vvar]
7ffd4d1fe000-7ffd4d200000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted (core dumped)
[/code]However, trying the same number with 4 threads instead of 8 on the same machine worked.

I'll try the trunk version for my 8 thread machines?

Thanks everyone.

EdH 2018-04-27 02:42

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 2-3% 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]hard/software info:
[code]
04/26/18 22:29:46 v1.34.5 @ math94, System/Build Info:
Using GMP-ECM 7.0.4, Powered by GMP 6.1.2
detected Intel(R) Core(TM) i7-2600 CPU @ 3.40GHz
detected L1 = 32768 bytes, L2 = 8388608 bytes, CL = 64 bytes
measured cpu frequency ~= 3392.234920[/code]Ok, I'm at a loss as to which way I go with these machines. I hate to cripple all of them to 4 cores. But, I also think I missed a lot of composites that had been processed by these and returned errors.

EdH 2018-04-27 03:30

[QUOTE=chris2be8;486293]Try "stty echo" (you will need to type it blind), next time you get into that state.

If that fails "stty sane" might fix it.

Chris[/QUOTE]
stty echo worked great. Thanks!

Dubslow 2018-04-27 04:31

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]

where in my bash aliases I have the following:

[code]
alias num='head -n 1 nfs.job | cut -d " " -f 2 > num'
alias yafusieve='~/yafu/yafu "nfs($(cat num))" -ns'
[/code]
... as well as [c]R=1[/c] in yafu.ini.

^Z to pause aliqueit, "manually" get yafu to do the over-the-hump sieving, then resume aliqueit and cancel the "auto increasing" ECM; it will restart another yafu, which (with [c]R=1[/c]) will detect the rels file and restart with filtering, this time succeeding thanks to the extra sieving.


All times are UTC. The time now is 08:15.

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