Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic)

EdH · 2020-04-06, 15:09

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

bsquared · 2020-04-06, 16:54

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.

VBCurtis · 2020-04-06, 19:15

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!

EdH · 2020-04-06, 20:51

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

EdH · 2020-04-06, 20:55

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?

EdH · 2020-04-07, 00:15

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.

EdH · 2020-04-07, 00:51

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?

VBCurtis · 2020-04-07, 02:08

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.

EdH · 2020-04-07, 03:02

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

VBCurtis · 2020-04-07, 03:11

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

EdH · 2020-04-07, 03:16

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
Solving Quartic Equation with a Coefficient of 1 MB Space	Andrew99	PARI/GP	32	2020-03-21 19:36
What should the "q" value increase to for GNFS/SNFS computations?	2147483647	Factoring	2	2016-12-10 08:42
Don't fear the quartic	fivemack	Factoring	6	2011-12-12 05:08
Quartic: Parameters	R.D. Silverman	Factoring	9	2009-02-18 23:24
GNFS or SNFS for Fib(1009) ?	fivemack	Factoring	6	2007-08-06 07:25

2020-04-06, 16:54	#2
bsquared "Ben" Feb 2007 2²×941 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 2×3²×17×19 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-07, 03:11	#10
VBCurtis "Curtis" Feb 2005 Riverside, CA 2·3²·17·19 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...