mersenneforum.org > EdH Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic)
 Register FAQ Search Today's Posts Mark Forums Read

 2020-04-06, 15:09 #1 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 3,617 Posts Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) This post is really being written as a reminder to myself, to not do this a third time. I followed through to an impending completion, as an experiment and to provide the following for anyone that may be interested. First, let me mention I have "a few" machines that together can factor 150 digit numbers in about a day. I had run an snfs job with a quatic in the past and experienced a rough time with it. The size of that composite had been 185 digits, but as an snfs it was flagged as being equivalent to a gnfs 153 digit job. It gave me quite a time, as referenced here. But, I'm stubborn and curious on occasion, so I ventured again. This is a description of that experience. This time the composite is "only" 168 digits, but it is considered to be equivalent to a 158 digit gnfs, if done with snfs, except that snfs would require a quartic. So, I decided to see how bad it could be doing this as an snfs job. Shouldn't be but a few days extra, right? How about a month! (Actually, only three extra weeks) After ten days, when I could finally build a matrix, CADO-NFS was memory bound and giving no indication of life. My normal runs include a separate machine which takes over with msieve once a matrix is viable. This machine, which also acts as a backup if the CADO-NFS machine hard crashes, runs msieve LA in parallel to the CADO-NFS server. I usually let it finish the factoring, since it is always showing an earlier return and it was showing a completion time: Code: linear algebra at 0.0%, ETA 562h 6m What!! Ten days sieving and now 24 more days before factors are produced? That's over a month! Since I was considering this an experiment, I ran sieving an extra day to see what effect I could produce on the matrix. It was a good choice. After one extra day of sieving, msieve showed the following completion time: Code: linear algebra at 0.0%, ETA 420h22m That's more like it. Only a total of 29 days. Less than most months now. But, to be more complete, once I had an impending completion under way, with a visible date, I ran the same number on all the same hardware as a gnfs job. After just over two days, I have a matrix and LA under way, although this time the CADO-NFS system crashed for lack of memory. The msieve system (same CPU/RAM as the CADO-NFS machine) is humming along, with a completion estimate of: Code: linear algebra at 0.0%, ETA 167h40m Two days sieving and seven in LA is quite a difference from a month long job. May I remember this in the future! In case there is interest, I am providing some log portions. Original msieve for snfs job: Code: Thu Apr 2 20:29:11 2020 found 6996515 hash collisions in 178055331 relations Thu Apr 2 20:29:19 2020 added 3657741 free relations Thu Apr 2 20:29:19 2020 commencing duplicate removal, pass 2 Thu Apr 2 21:15:02 2020 found 0 duplicates and 181713072 unique relations Thu Apr 2 21:15:02 2020 memory use: 522.4 MB Thu Apr 2 21:15:02 2020 reading ideals above 82116608 Thu Apr 2 21:15:02 2020 commencing singleton removal, initial pass Thu Apr 2 21:31:04 2020 memory use: 5512.0 MB Thu Apr 2 21:31:05 2020 reading all ideals from disk Thu Apr 2 21:32:02 2020 memory use: 4021.8 MB Thu Apr 2 21:32:11 2020 commencing in-memory singleton removal Thu Apr 2 21:32:20 2020 begin with 181713072 relations and 184298049 unique ideals Thu Apr 2 21:34:02 2020 reduce to 85784830 relations and 75250832 ideals in 20 passes Thu Apr 2 21:34:02 2020 max relations containing the same ideal: 33 Thu Apr 2 21:34:07 2020 reading ideals above 720000 Thu Apr 2 21:34:07 2020 commencing singleton removal, initial pass Thu Apr 2 22:28:07 2020 memory use: 2756.0 MB Thu Apr 2 22:28:07 2020 reading all ideals from disk Thu Apr 2 22:29:21 2020 memory use: 3390.7 MB Thu Apr 2 22:29:31 2020 keeping 84371002 ideals with weight <= 200, target excess is 451006 Thu Apr 2 22:29:40 2020 commencing in-memory singleton removal Thu Apr 2 22:29:48 2020 begin with 85784830 relations and 84371002 unique ideals Thu Apr 2 22:30:49 2020 reduce to 85783651 relations and 84369819 ideals in 8 passes Thu Apr 2 22:30:49 2020 max relations containing the same ideal: 200 Thu Apr 2 22:31:30 2020 removing 4690784 relations and 4290785 ideals in 400000 cliques Thu Apr 2 22:31:32 2020 commencing in-memory singleton removal Thu Apr 2 22:31:39 2020 begin with 81092867 relations and 84369819 unique ideals Thu Apr 2 22:32:51 2020 reduce to 80877726 relations and 79862226 ideals in 10 passes Thu Apr 2 22:32:51 2020 max relations containing the same ideal: 199 Thu Apr 2 22:33:29 2020 removing 3424705 relations and 3024705 ideals in 400000 cliques Thu Apr 2 22:33:30 2020 commencing in-memory singleton removal Thu Apr 2 22:33:37 2020 begin with 77453021 relations and 79862226 unique ideals Thu Apr 2 22:34:39 2020 reduce to 77327055 relations and 76710820 ideals in 9 passes Thu Apr 2 22:34:39 2020 max relations containing the same ideal: 193 Thu Apr 2 22:35:15 2020 removing 876360 relations and 783292 ideals in 93068 cliques Thu Apr 2 22:35:16 2020 commencing in-memory singleton removal Thu Apr 2 22:35:23 2020 begin with 76450695 relations and 76710820 unique ideals Thu Apr 2 22:36:10 2020 reduce to 76442305 relations and 75919123 ideals in 7 passes Thu Apr 2 22:36:10 2020 max relations containing the same ideal: 192 Thu Apr 2 22:36:28 2020 relations with 0 large ideals: 36726 Thu Apr 2 22:36:28 2020 relations with 1 large ideals: 3767 Thu Apr 2 22:36:28 2020 relations with 2 large ideals: 37771 Thu Apr 2 22:36:28 2020 relations with 3 large ideals: 360661 Thu Apr 2 22:36:28 2020 relations with 4 large ideals: 2098967 Thu Apr 2 22:36:28 2020 relations with 5 large ideals: 10292745 Thu Apr 2 22:36:28 2020 relations with 6 large ideals: 15869580 Thu Apr 2 22:36:28 2020 relations with 7+ large ideals: 47742088 Thu Apr 2 22:36:28 2020 commencing 2-way merge Thu Apr 2 22:37:22 2020 reduce to 47991601 relation sets and 47468419 unique ideals Thu Apr 2 22:37:22 2020 commencing full merge Thu Apr 2 22:51:18 2020 memory use: 5441.1 MB Thu Apr 2 22:51:23 2020 found 25475149 cycles, need 25414619 Thu Apr 2 22:51:32 2020 weight of 25414619 cycles is about 1779046605 (70.00/cycle) Thu Apr 2 22:51:32 2020 distribution of cycle lengths: Thu Apr 2 22:51:32 2020 1 relations: 3578896 Thu Apr 2 22:51:32 2020 2 relations: 3616742 Thu Apr 2 22:51:32 2020 3 relations: 3277170 Thu Apr 2 22:51:32 2020 4 relations: 2782082 Thu Apr 2 22:51:32 2020 5 relations: 2304783 Thu Apr 2 22:51:32 2020 6 relations: 1908219 Thu Apr 2 22:51:32 2020 7 relations: 1558181 Thu Apr 2 22:51:32 2020 8 relations: 1261792 Thu Apr 2 22:51:32 2020 9 relations: 1021589 Thu Apr 2 22:51:32 2020 10+ relations: 4105165 Thu Apr 2 22:51:32 2020 heaviest cycle: 28 relations Thu Apr 2 22:51:38 2020 commencing cycle optimization Thu Apr 2 22:52:13 2020 start with 139878518 relations Thu Apr 2 22:55:46 2020 pruned 2881999 relations Thu Apr 2 22:55:49 2020 memory use: 4583.5 MB Thu Apr 2 22:55:49 2020 distribution of cycle lengths: Thu Apr 2 22:55:49 2020 1 relations: 3578896 Thu Apr 2 22:55:49 2020 2 relations: 3674442 Thu Apr 2 22:55:49 2020 3 relations: 3377551 Thu Apr 2 22:55:49 2020 4 relations: 2832766 Thu Apr 2 22:55:49 2020 5 relations: 2344336 Thu Apr 2 22:55:49 2020 6 relations: 1915354 Thu Apr 2 22:55:49 2020 7 relations: 1554156 Thu Apr 2 22:55:49 2020 8 relations: 1246009 Thu Apr 2 22:55:49 2020 9 relations: 1002246 Thu Apr 2 22:55:49 2020 10+ relations: 3888863 Thu Apr 2 22:55:49 2020 heaviest cycle: 28 relations Thu Apr 2 22:56:25 2020 RelProcTime: 10610 Thu Apr 2 22:56:36 2020 Thu Apr 2 22:56:36 2020 commencing linear algebra Thu Apr 2 22:56:38 2020 read 25414619 cycles Thu Apr 2 22:57:15 2020 cycles contain 75921473 unique relations Thu Apr 2 23:41:55 2020 read 75921473 relations Thu Apr 2 23:43:47 2020 using 20 quadratic characters above 4294917295 Thu Apr 2 23:49:08 2020 building initial matrix Thu Apr 2 23:58:44 2020 memory use: 9421.6 MB Fri Apr 3 00:05:58 2020 read 25414619 cycles Fri Apr 3 00:06:03 2020 matrix is 25414441 x 25414619 (7685.6 MB) with weight 2218031685 (87.27/col) Fri Apr 3 00:06:03 2020 sparse part has weight 1735168418 (68.27/col) Fri Apr 3 00:10:43 2020 filtering completed in 2 passes Fri Apr 3 00:10:48 2020 matrix is 25404923 x 25405100 (7685.0 MB) with weight 2217789664 (87.30/col) Fri Apr 3 00:10:48 2020 sparse part has weight 1735111710 (68.30/col) Fri Apr 3 00:21:09 2020 matrix starts at (0, 0) Fri Apr 3 00:21:12 2020 matrix is 25404923 x 25405100 (7685.0 MB) with weight 2217789664 (87.30/col) Fri Apr 3 00:21:12 2020 sparse part has weight 1735111710 (68.30/col) Fri Apr 3 00:21:12 2020 saving the first 48 matrix rows for later Fri Apr 3 00:21:16 2020 matrix includes 64 packed rows Fri Apr 3 00:21:20 2020 matrix is 25404875 x 25405100 (7334.9 MB) with weight 1796131098 (70.70/col) Fri Apr 3 00:21:20 2020 sparse part has weight 1668742038 (65.69/col) Fri Apr 3 00:21:20 2020 using block size 8192 and superblock size 786432 for processor cache size 8192 kB Fri Apr 3 00:23:21 2020 commencing Lanczos iteration (8 threads) Fri Apr 3 00:23:21 2020 memory use: 6228.2 MB Fri Apr 3 00:25:28 2020 linear algebra at 0.0%, ETA 562h 6m Second msieve matrix, after adding another day's worth of relations: Code: Fri Apr 3 08:29:59 2020 found 7515640 hash collisions in 184734997 relations Fri Apr 3 08:30:07 2020 added 3657741 free relations Fri Apr 3 08:30:07 2020 commencing duplicate removal, pass 2 Fri Apr 3 08:35:37 2020 found 0 duplicates and 188392738 unique relations Fri Apr 3 08:35:37 2020 memory use: 522.4 MB Fri Apr 3 08:35:37 2020 reading ideals above 86573056 Fri Apr 3 08:35:37 2020 commencing singleton removal, initial pass Fri Apr 3 08:48:57 2020 memory use: 5512.0 MB Fri Apr 3 08:48:57 2020 reading all ideals from disk Fri Apr 3 08:49:24 2020 memory use: 4137.7 MB Fri Apr 3 08:49:33 2020 commencing in-memory singleton removal Fri Apr 3 08:49:42 2020 begin with 188392738 relations and 186264462 unique ideals Fri Apr 3 08:51:16 2020 reduce to 95263346 relations and 81126535 ideals in 17 passes Fri Apr 3 08:51:16 2020 max relations containing the same ideal: 34 Fri Apr 3 08:51:22 2020 reading ideals above 720000 Fri Apr 3 08:51:22 2020 commencing singleton removal, initial pass Fri Apr 3 09:00:38 2020 memory use: 2756.0 MB Fri Apr 3 09:00:39 2020 reading all ideals from disk Fri Apr 3 09:01:03 2020 memory use: 3770.9 MB Fri Apr 3 09:01:14 2020 keeping 90681904 ideals with weight <= 200, target excess is 503859 Fri Apr 3 09:01:25 2020 commencing in-memory singleton removal Fri Apr 3 09:01:33 2020 begin with 95263346 relations and 90681904 unique ideals Fri Apr 3 09:02:23 2020 reduce to 95262520 relations and 90681076 ideals in 6 passes Fri Apr 3 09:02:23 2020 max relations containing the same ideal: 200 Fri Apr 3 09:03:07 2020 removing 4376947 relations and 3976948 ideals in 400000 cliques Fri Apr 3 09:03:09 2020 commencing in-memory singleton removal Fri Apr 3 09:03:17 2020 begin with 90885573 relations and 90681076 unique ideals Fri Apr 3 09:04:38 2020 reduce to 90727470 relations and 86544948 ideals in 10 passes Fri Apr 3 09:04:38 2020 max relations containing the same ideal: 199 Fri Apr 3 09:05:19 2020 removing 3205222 relations and 2805222 ideals in 400000 cliques Fri Apr 3 09:05:21 2020 commencing in-memory singleton removal Fri Apr 3 09:05:29 2020 begin with 87522248 relations and 86544948 unique ideals Fri Apr 3 09:06:39 2020 reduce to 87430757 relations and 83647732 ideals in 9 passes Fri Apr 3 09:06:39 2020 max relations containing the same ideal: 197 Fri Apr 3 09:07:18 2020 removing 2831556 relations and 2431556 ideals in 400000 cliques Fri Apr 3 09:07:20 2020 commencing in-memory singleton removal Fri Apr 3 09:07:28 2020 begin with 84599201 relations and 83647732 unique ideals Fri Apr 3 09:08:20 2020 reduce to 84524726 relations and 81141323 ideals in 7 passes Fri Apr 3 09:08:20 2020 max relations containing the same ideal: 193 Fri Apr 3 09:08:58 2020 removing 2616153 relations and 2216153 ideals in 400000 cliques Fri Apr 3 09:09:00 2020 commencing in-memory singleton removal Fri Apr 3 09:09:07 2020 begin with 81908573 relations and 81141323 unique ideals Fri Apr 3 09:09:58 2020 reduce to 81842732 relations and 78858987 ideals in 7 passes Fri Apr 3 09:09:58 2020 max relations containing the same ideal: 190 Fri Apr 3 09:10:35 2020 removing 2476265 relations and 2076265 ideals in 400000 cliques Fri Apr 3 09:10:36 2020 commencing in-memory singleton removal Fri Apr 3 09:10:43 2020 begin with 79366467 relations and 78858987 unique ideals Fri Apr 3 09:11:32 2020 reduce to 79305871 relations and 76721826 ideals in 7 passes Fri Apr 3 09:11:32 2020 max relations containing the same ideal: 189 Fri Apr 3 09:12:08 2020 removing 2372749 relations and 1972749 ideals in 400000 cliques Fri Apr 3 09:12:09 2020 commencing in-memory singleton removal Fri Apr 3 09:12:16 2020 begin with 76933122 relations and 76721826 unique ideals Fri Apr 3 09:13:03 2020 reduce to 76874240 relations and 74689898 ideals in 7 passes Fri Apr 3 09:13:03 2020 max relations containing the same ideal: 182 Fri Apr 3 09:13:38 2020 removing 2291357 relations and 1891357 ideals in 400000 cliques Fri Apr 3 09:13:39 2020 commencing in-memory singleton removal Fri Apr 3 09:13:46 2020 begin with 74582883 relations and 74689898 unique ideals Fri Apr 3 09:14:32 2020 reduce to 74526812 relations and 72742209 ideals in 7 passes Fri Apr 3 09:14:32 2020 max relations containing the same ideal: 179 Fri Apr 3 09:15:05 2020 removing 2226430 relations and 1826430 ideals in 400000 cliques Fri Apr 3 09:15:07 2020 commencing in-memory singleton removal Fri Apr 3 09:15:13 2020 begin with 72300382 relations and 72742209 unique ideals Fri Apr 3 09:15:57 2020 reduce to 72244780 relations and 70859867 ideals in 7 passes Fri Apr 3 09:15:57 2020 max relations containing the same ideal: 178 Fri Apr 3 09:16:30 2020 removing 2176939 relations and 1776939 ideals in 400000 cliques Fri Apr 3 09:16:31 2020 commencing in-memory singleton removal Fri Apr 3 09:16:38 2020 begin with 70067841 relations and 70859867 unique ideals Fri Apr 3 09:17:20 2020 reduce to 70012791 relations and 69027605 ideals in 7 passes Fri Apr 3 09:17:20 2020 max relations containing the same ideal: 171 Fri Apr 3 09:17:52 2020 removing 2138900 relations and 1738900 ideals in 400000 cliques Fri Apr 3 09:17:53 2020 commencing in-memory singleton removal Fri Apr 3 09:17:59 2020 begin with 67873891 relations and 69027605 unique ideals Fri Apr 3 09:18:41 2020 reduce to 67818603 relations and 67233106 ideals in 7 passes Fri Apr 3 09:18:41 2020 max relations containing the same ideal: 166 Fri Apr 3 09:19:22 2020 relations with 0 large ideals: 40956 Fri Apr 3 09:19:22 2020 relations with 1 large ideals: 4638 Fri Apr 3 09:19:22 2020 relations with 2 large ideals: 50650 Fri Apr 3 09:19:22 2020 relations with 3 large ideals: 450368 Fri Apr 3 09:19:22 2020 relations with 4 large ideals: 2400538 Fri Apr 3 09:19:22 2020 relations with 5 large ideals: 10328086 Fri Apr 3 09:19:22 2020 relations with 6 large ideals: 15188890 Fri Apr 3 09:19:22 2020 relations with 7+ large ideals: 39354477 Fri Apr 3 09:19:22 2020 commencing 2-way merge Fri Apr 3 09:20:08 2020 reduce to 44136312 relation sets and 43550815 unique ideals Fri Apr 3 09:20:08 2020 commencing full merge Fri Apr 3 09:31:50 2020 memory use: 4957.3 MB Fri Apr 3 09:31:55 2020 found 23307636 cycles, need 23229015 Fri Apr 3 09:32:02 2020 weight of 23229015 cycles is about 1626265736 (70.01/cycle) Fri Apr 3 09:32:02 2020 distribution of cycle lengths: Fri Apr 3 09:32:02 2020 1 relations: 2773895 Fri Apr 3 09:32:02 2020 2 relations: 3069001 Fri Apr 3 09:32:02 2020 3 relations: 2961763 Fri Apr 3 09:32:02 2020 4 relations: 2609352 Fri Apr 3 09:32:02 2020 5 relations: 2230528 Fri Apr 3 09:32:02 2020 6 relations: 1903759 Fri Apr 3 09:32:02 2020 7 relations: 1609057 Fri Apr 3 09:32:02 2020 8 relations: 1344397 Fri Apr 3 09:32:02 2020 9 relations: 1110508 Fri Apr 3 09:32:02 2020 10+ relations: 3616755 Fri Apr 3 09:32:02 2020 heaviest cycle: 25 relations Fri Apr 3 09:32:07 2020 commencing cycle optimization Fri Apr 3 09:32:40 2020 start with 127551950 relations Fri Apr 3 09:35:44 2020 pruned 2831870 relations Fri Apr 3 09:35:46 2020 memory use: 4128.5 MB Fri Apr 3 09:35:47 2020 distribution of cycle lengths: Fri Apr 3 09:35:47 2020 1 relations: 2773895 Fri Apr 3 09:35:47 2020 2 relations: 3120353 Fri Apr 3 09:35:47 2020 3 relations: 3057234 Fri Apr 3 09:35:47 2020 4 relations: 2664748 Fri Apr 3 09:35:47 2020 5 relations: 2277223 Fri Apr 3 09:35:47 2020 6 relations: 1921958 Fri Apr 3 09:35:47 2020 7 relations: 1616005 Fri Apr 3 09:35:47 2020 8 relations: 1336440 Fri Apr 3 09:35:47 2020 9 relations: 1097517 Fri Apr 3 09:35:47 2020 10+ relations: 3363642 Fri Apr 3 09:35:47 2020 heaviest cycle: 25 relations Fri Apr 3 09:36:19 2020 RelProcTime: 5157 Fri Apr 3 09:36:28 2020 Fri Apr 3 09:36:28 2020 commencing linear algebra Fri Apr 3 09:36:30 2020 read 23229015 cycles Fri Apr 3 09:37:03 2020 cycles contain 67374603 unique relations Fri Apr 3 09:42:51 2020 read 67374603 relations Fri Apr 3 09:44:30 2020 using 20 quadratic characters above 4294917295 Fri Apr 3 09:49:15 2020 building initial matrix Fri Apr 3 09:57:33 2020 memory use: 8486.7 MB Fri Apr 3 09:57:50 2020 read 23229015 cycles Fri Apr 3 09:57:54 2020 matrix is 23228836 x 23229015 (7021.2 MB) with weight 2029783302 (87.38/col) Fri Apr 3 09:57:54 2020 sparse part has weight 1585047168 (68.24/col) Fri Apr 3 10:01:24 2020 filtering completed in 2 passes Fri Apr 3 10:01:29 2020 matrix is 23221679 x 23221857 (7020.8 MB) with weight 2029612756 (87.40/col) Fri Apr 3 10:01:29 2020 sparse part has weight 1585009883 (68.26/col) Fri Apr 3 10:03:06 2020 matrix starts at (0, 0) Fri Apr 3 10:03:09 2020 matrix is 23221679 x 23221857 (7020.8 MB) with weight 2029612756 (87.40/col) Fri Apr 3 10:03:09 2020 sparse part has weight 1585009883 (68.26/col) Fri Apr 3 10:03:09 2020 saving the first 48 matrix rows for later Fri Apr 3 10:03:12 2020 matrix includes 64 packed rows Fri Apr 3 10:03:15 2020 matrix is 23221631 x 23221857 (6699.3 MB) with weight 1641596008 (70.69/col) Fri Apr 3 10:03:15 2020 sparse part has weight 1523960763 (65.63/col) Fri Apr 3 10:03:15 2020 using block size 8192 and superblock size 786432 for processor cache size 8192 kB Fri Apr 3 10:04:59 2020 commencing Lanczos iteration (8 threads) Fri Apr 3 10:04:59 2020 memory use: 5674.3 MB Fri Apr 3 10:06:42 2020 linear algebra at 0.0%, ETA 420h22m gnfs msieve completion run: Code: Sun Apr 5 20:54:15 2020 found 34959463 hash collisions in 154461306 relations Sun Apr 5 20:54:47 2020 added 121840 free relations Sun Apr 5 20:54:47 2020 commencing duplicate removal, pass 2 Sun Apr 5 20:58:26 2020 found 36940296 duplicates and 117642850 unique relations Sun Apr 5 20:58:26 2020 memory use: 724.8 MB Sun Apr 5 20:58:26 2020 reading ideals above 100990976 Sun Apr 5 20:58:26 2020 commencing singleton removal, initial pass Sun Apr 5 21:09:33 2020 memory use: 3012.0 MB Sun Apr 5 21:09:34 2020 reading all ideals from disk Sun Apr 5 21:09:38 2020 memory use: 2107.7 MB Sun Apr 5 21:09:42 2020 commencing in-memory singleton removal Sun Apr 5 21:09:46 2020 begin with 117642850 relations and 114293681 unique ideals Sun Apr 5 21:10:38 2020 reduce to 55056997 relations and 43084650 ideals in 21 passes Sun Apr 5 21:10:38 2020 max relations containing the same ideal: 32 Sun Apr 5 21:10:41 2020 reading ideals above 720000 Sun Apr 5 21:10:41 2020 commencing singleton removal, initial pass Sun Apr 5 21:18:27 2020 memory use: 1506.0 MB Sun Apr 5 21:18:27 2020 reading all ideals from disk Sun Apr 5 21:18:35 2020 memory use: 2105.4 MB Sun Apr 5 21:18:41 2020 keeping 54416437 ideals with weight <= 200, target excess is 281673 Sun Apr 5 21:18:46 2020 commencing in-memory singleton removal Sun Apr 5 21:18:51 2020 begin with 55056997 relations and 54416437 unique ideals Sun Apr 5 21:20:18 2020 reduce to 54809978 relations and 54169296 ideals in 19 passes Sun Apr 5 21:20:18 2020 max relations containing the same ideal: 200 Sun Apr 5 21:20:43 2020 removing 2496411 relations and 2339440 ideals in 156971 cliques Sun Apr 5 21:20:44 2020 commencing in-memory singleton removal Sun Apr 5 21:20:49 2020 begin with 52313567 relations and 54169296 unique ideals Sun Apr 5 21:21:37 2020 reduce to 52195905 relations and 51711588 ideals in 11 passes Sun Apr 5 21:21:37 2020 max relations containing the same ideal: 199 Sun Apr 5 21:22:01 2020 removing 1813236 relations and 1656265 ideals in 156971 cliques Sun Apr 5 21:22:02 2020 commencing in-memory singleton removal Sun Apr 5 21:22:06 2020 begin with 50382669 relations and 51711588 unique ideals Sun Apr 5 21:22:52 2020 reduce to 50316386 relations and 49988736 ideals in 11 passes Sun Apr 5 21:22:52 2020 max relations containing the same ideal: 195 Sun Apr 5 21:23:23 2020 relations with 0 large ideals: 1034 Sun Apr 5 21:23:23 2020 relations with 1 large ideals: 856 Sun Apr 5 21:23:23 2020 relations with 2 large ideals: 18424 Sun Apr 5 21:23:23 2020 relations with 3 large ideals: 203791 Sun Apr 5 21:23:23 2020 relations with 4 large ideals: 1236187 Sun Apr 5 21:23:23 2020 relations with 5 large ideals: 4513073 Sun Apr 5 21:23:23 2020 relations with 6 large ideals: 10313781 Sun Apr 5 21:23:23 2020 relations with 7+ large ideals: 34029240 Sun Apr 5 21:23:23 2020 commencing 2-way merge Sun Apr 5 21:23:59 2020 reduce to 29678051 relation sets and 29350427 unique ideals Sun Apr 5 21:23:59 2020 ignored 26 oversize relation sets Sun Apr 5 21:23:59 2020 commencing full merge Sun Apr 5 21:31:31 2020 memory use: 3222.4 MB Sun Apr 5 21:31:34 2020 found 15606415 cycles, need 15584627 Sun Apr 5 21:31:39 2020 weight of 15584627 cycles is about 1091087653 (70.01/cycle) Sun Apr 5 21:31:39 2020 distribution of cycle lengths: Sun Apr 5 21:31:39 2020 1 relations: 2621515 Sun Apr 5 21:31:39 2020 2 relations: 2310585 Sun Apr 5 21:31:39 2020 3 relations: 2076426 Sun Apr 5 21:31:39 2020 4 relations: 1677438 Sun Apr 5 21:31:39 2020 5 relations: 1428115 Sun Apr 5 21:31:39 2020 6 relations: 1132838 Sun Apr 5 21:31:39 2020 7 relations: 889951 Sun Apr 5 21:31:39 2020 8 relations: 701441 Sun Apr 5 21:31:39 2020 9 relations: 559643 Sun Apr 5 21:31:39 2020 10+ relations: 2186675 Sun Apr 5 21:31:39 2020 heaviest cycle: 28 relations Sun Apr 5 21:31:42 2020 commencing cycle optimization Sun Apr 5 21:32:04 2020 start with 81078992 relations Sun Apr 5 21:33:38 2020 pruned 1396654 relations Sun Apr 5 21:33:39 2020 memory use: 2862.5 MB Sun Apr 5 21:33:39 2020 distribution of cycle lengths: Sun Apr 5 21:33:39 2020 1 relations: 2621515 Sun Apr 5 21:33:39 2020 2 relations: 2356643 Sun Apr 5 21:33:39 2020 3 relations: 2136024 Sun Apr 5 21:33:39 2020 4 relations: 1699429 Sun Apr 5 21:33:39 2020 5 relations: 1437714 Sun Apr 5 21:33:39 2020 6 relations: 1125763 Sun Apr 5 21:33:39 2020 7 relations: 879256 Sun Apr 5 21:33:39 2020 8 relations: 688558 Sun Apr 5 21:33:39 2020 9 relations: 546635 Sun Apr 5 21:33:39 2020 10+ relations: 2093090 Sun Apr 5 21:33:39 2020 heaviest cycle: 28 relations Sun Apr 5 21:34:00 2020 RelProcTime: 3567 Sun Apr 5 21:34:06 2020 Sun Apr 5 21:34:06 2020 commencing linear algebra Sun Apr 5 21:34:07 2020 read 15584627 cycles Sun Apr 5 21:34:30 2020 cycles contain 49790191 unique relations Sun Apr 5 21:39:50 2020 read 49790191 relations Sun Apr 5 21:40:54 2020 using 20 quadratic characters above 4294917295 Sun Apr 5 21:44:24 2020 building initial matrix Sun Apr 5 21:50:49 2020 memory use: 6730.9 MB Sun Apr 5 21:50:55 2020 read 15584627 cycles Sun Apr 5 21:50:58 2020 matrix is 15584449 x 15584627 (4760.7 MB) with weight 1475583892 (94.68/col) Sun Apr 5 21:50:58 2020 sparse part has weight 1060979235 (68.08/col) Sun Apr 5 21:53:36 2020 filtering completed in 2 passes Sun Apr 5 21:53:39 2020 matrix is 15572515 x 15572693 (4759.8 MB) with weight 1475144721 (94.73/col) Sun Apr 5 21:53:39 2020 sparse part has weight 1060890475 (68.13/col) Sun Apr 5 21:54:50 2020 matrix starts at (0, 0) Sun Apr 5 21:54:53 2020 matrix is 15572515 x 15572693 (4759.8 MB) with weight 1475144721 (94.73/col) Sun Apr 5 21:54:53 2020 sparse part has weight 1060890475 (68.13/col) Sun Apr 5 21:54:53 2020 saving the first 48 matrix rows for later Sun Apr 5 21:54:55 2020 matrix includes 64 packed rows Sun Apr 5 21:54:57 2020 matrix is 15572467 x 15572693 (4581.6 MB) with weight 1174515019 (75.42/col) Sun Apr 5 21:54:57 2020 sparse part has weight 1045302898 (67.12/col) Sun Apr 5 21:54:57 2020 using block size 8192 and superblock size 786432 for processor cache size 8192 kB Sun Apr 5 21:55:57 2020 commencing Lanczos iteration (8 threads) Sun Apr 5 21:55:57 2020 memory use: 3775.8 MB Sun Apr 5 21:56:59 2020 linear algebra at 0.0%, ETA 167h40m Last fiddled with by EdH on 2020-04-06 at 16:12
 2020-04-06, 16:54 #2 bsquared     "Ben" Feb 2007 3,371 Posts Can I ask what input number you used for this experiment? I'd like to see what yafu does by default with it. It has some machinery for deciding between gnfs and snfs and this experience may help adjust it, if necessary, when facing quartics.
 2020-04-06, 19:15 #3 VBCurtis     "Curtis" Feb 2005 Riverside, CA 33×173 Posts Once the matrix sizes exceed 10M, I think it's pretty important to get off the default matrix density of 70. If you retained the data, I suggest you explore this by setting the flag target_density=100 in your msieve filtering invocation. I've found positive results (measured by matrix ETA) up to density 120, while the NFS@home solvers often use 130 or even 140. I think most of the gains come going from 70 to 90 or 100. A pleasant (and possibly more important side effect) is that it's harder to build a matrix with higher density, which acts as a nice measure of whether you have "oversieved enough". Your second msieve run will almost surely build at TD 100, and I bet the matrix will be smaller by 1M dimensions or so. That might only take a day off the matrix ETA, but saving a day for "free" is still worthy!
2020-04-06, 20:51   #4
EdH

"Ed Hall"
Dec 2009

3,617 Posts

Quote:
 Originally Posted by bsquared Can I ask what input number you used for this experiment? I'd like to see what yafu does by default with it. It has some machinery for deciding between gnfs and snfs and this experience may help adjust it, if necessary, when facing quartics.
The composite was:
Code:
182020007230135528991139915341347872965880609847705423888116875025588252350522154240713634227215698881699545439356408616763969093995140732452346538717063179710306355261
from HCN 6+5,370. In fact, I used:
Code:
./yafu "snfs(6^370+5^370,182020007230135528991139915341347872965880609847705423888116875025588252350522154240713634227215698881699545439356408616763969093995140732452346538717063179710306355261)" -v -np
to generate the polynomial:
Code:
n: 182020007230135528991139915341347872965880609847705423888116875025588252350522154240713634227215698881699545439356408616763969093995140732452346538717063179710306355261
skew: 1.0000
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
Y1: -5293955920339377119177015629247762262821197509765625
Y0: 3829944921253794893077685127088430174646042802674934480896

2020-04-06, 20:55   #5
EdH

"Ed Hall"
Dec 2009

3,617 Posts

Quote:
 Originally Posted by VBCurtis Once the matrix sizes exceed 10M, I think it's pretty important to get off the default matrix density of 70. If you retained the data, I suggest you explore this by setting the flag target_density=100 in your msieve filtering invocation. I've found positive results (measured by matrix ETA) up to density 120, while the NFS@home solvers often use 130 or even 140. I think most of the gains come going from 70 to 90 or 100. A pleasant (and possibly more important side effect) is that it's harder to build a matrix with higher density, which acts as a nice measure of whether you have "oversieved enough". Your second msieve run will almost surely build at TD 100, and I bet the matrix will be smaller by 1M dimensions or so. That might only take a day off the matrix ETA, but saving a day for "free" is still worthy!
I should be able to give this a try. I haven't cleaned up anything yet and will be interrupting all the snfs in favor of letting the gnfs run to completion.

BTW, are you working on Improved params for the 165-175 digit range at all?

2020-04-07, 00:15   #6
EdH

"Ed Hall"
Dec 2009

70418 Posts

Quote:
 Originally Posted by VBCurtis I've just started back on building params files, with an eye toward extending the patterns of what-increases-when from the C100-140 files up into C160. Let me know what size you'd like, I'll be happy to put one together for you! I'm running trials personally on C130-140 presently to refine those files and test A=26 vs I=13 and I=14; I think 165-170 will be a spot to test I=14 vs A=28, and I would appreciate some testing of that setting on one of my params files.
The one I've got running LA right now is a 168 dd HCN, for which I used the default 170 params file. The trouble I foresee is that my CADO-NFS server crashed with memory woes. My hybrid CADO/msieve setup would not give you complete data and that is what I would probably need to use for the 175-176 HCNs that are next in line.

However, if you'd like to just toss something together roughly for me at the 175 level, I could see how a 175/176 compares to the 168 I'm currently finishing. You could maybe slant it toward my large siever count vs. single LA machine.

I wish I kept better notes! I'm pretty sure I found that I could still use mpi to run msieve LA across two machines, if one didn't have enough memory. I only have gigabit currently and am pretty sure that caused a bit of slow-down, but wasn't excessive for just two nodes. That may very well only be "wishful thinking," though.

2020-04-07, 00:51   #7
EdH

"Ed Hall"
Dec 2009

3,617 Posts

Quote:
 Originally Posted by VBCurtis Once the matrix sizes exceed 10M, I think it's pretty important to get off the default matrix density of 70. If you retained the data, I suggest you explore this by setting the flag target_density=100 in your msieve filtering invocation. I've found positive results (measured by matrix ETA) up to density 120, while the NFS@home solvers often use 130 or even 140. I think most of the gains come going from 70 to 90 or 100. A pleasant (and possibly more important side effect) is that it's harder to build a matrix with higher density, which acts as a nice measure of whether you have "oversieved enough". Your second msieve run will almost surely build at TD 100, and I bet the matrix will be smaller by 1M dimensions or so. That might only take a day off the matrix ETA, but saving a day for "free" is still worthy!
Something didn't work for me with target_density=100. I have essentially the same matrix as before:
Code:
Mon Apr  6 20:39:00 2020  matrix is 23221679 x 23221857 (7020.8 MB) with weight 2029612756 (87.40/col)
Do I need to run -nc1 only with the target_density=100 and then -nc2, etc.? Msieve didn't complain when I ran -nc, but maybe it just skipped the target_density?

2020-04-07, 02:08   #8
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

33×173 Posts

Quote:
 Originally Posted by EdH Do I need to run -nc1 only with the target_density=100 and then -nc2, etc.? Msieve didn't complain when I ran -nc, but maybe it just skipped the target_density?
The log has the target density at the beginning, after the poly and "commencing relation filtering" line:
Code:
Fri Nov 15 22:05:29 2019  commencing relation filtering
Fri Nov 15 22:05:29 2019  setting target matrix density to 124.0
Fri Nov 15 22:05:29 2019  estimated available RAM is 15886.1 MB
Then, after the full merge at the end of the nc1 phase, you'll get a list of cycles with a weight that usually matches:
Code:
Sat Nov 16 02:42:26 2019  found 27238784 cycles, need 26022994
Sat Nov 16 02:42:31 2019  weight of 26022994 cycles is about 3227196741 (124.01/cycle)
If those don't match, something unusual is happening.

2020-04-07, 03:02   #9
EdH

"Ed Hall"
Dec 2009

3,617 Posts

Quote:
 Originally Posted by VBCurtis The log has the target density at the beginning, after the poly and "commencing relation filtering" line: Code: Fri Nov 15 22:05:29 2019 commencing relation filtering Fri Nov 15 22:05:29 2019 setting target matrix density to 124.0 Fri Nov 15 22:05:29 2019 estimated available RAM is 15886.1 MB Then, after the full merge at the end of the nc1 phase, you'll get a list of cycles with a weight that usually matches: Code: Sat Nov 16 02:42:26 2019 found 27238784 cycles, need 26022994 Sat Nov 16 02:42:31 2019 weight of 26022994 cycles is about 3227196741 (124.01/cycle) If those don't match, something unusual is happening.
I'm doing something wrong. There's no target density line in the log. Do I just put "target_density=100" (without quotes) within the call or after the -nc1?
Code:
../msieve -i comp.n -s comp.dat -l compmsieve.log -nf comp.fb -nc1 target_density=100

 2020-04-07, 03:11 #10 VBCurtis     "Curtis" Feb 2005 Riverside, CA 33·173 Posts If it doesn't work without quotes (just as you wrote it in the code box), try it with quotes! I know that for poly select invocations, multiple flags have to be put in quotes for -np1 to notice them all. Maybe the file-handling flags are making msieve ignore the TD flag? I forget...
2020-04-07, 03:16   #11
EdH

"Ed Hall"
Dec 2009

3,617 Posts

Quote:
 Originally Posted by VBCurtis If it doesn't work without quotes (just as you wrote it in the code box), try it with quotes! I know that for poly select invocations, multiple flags have to be put in quotes for -np1 to notice them all. Maybe the file-handling flags are making msieve ignore the TD flag? I forget...
I'll try a few different versions tomorrow. I looked through the msieve.nfs doc several times and couldn't find any specific example for the filtering options. "-target_density=100" (with the hyphen but without quotes) made it crash.

 Similar Threads Thread Thread Starter Forum Replies Last Post Andrew99 PARI/GP 32 2020-03-21 19:36 2147483647 Factoring 2 2016-12-10 08:42 fivemack Factoring 6 2011-12-12 05:08 R.D. Silverman Factoring 9 2009-02-18 23:24 fivemack Factoring 6 2007-08-06 07:25

All times are UTC. The time now is 01:34.

Sat Feb 27 01:34:02 UTC 2021 up 85 days, 21:45, 1 user, load averages: 2.51, 2.13, 2.23