C304_150_149

swellman · 2016-08-16, 10:50

Ryan Propper is attempting to factor C304_150_149, the granddaddy of the current xyyxf project. He ran ECM up to t65 with no factors appearing, selected the best SNFS poly via test sieving and has now sieved enough relations such that msieve builds a matrix and enters LA (@TD=130). Then the problems started...

Code:

Sat Aug 13 21:52:06 2016  skipped 857060 relations with b > 2^32
Sat Aug 13 21:52:06 2016  found 89207085 hash collisions in 684322003 relations
Sat Aug 13 21:52:29 2016  added 1218833 free relations
Sat Aug 13 21:52:29 2016  commencing duplicate removal, pass 2
Sun Aug 14 00:01:17 2016  found 2 duplicates and 685540834 unique relations
Sun Aug 14 00:01:17 2016  memory use: 4262.0 MB
Sun Aug 14 00:01:18 2016  reading ideals above 720000
Sun Aug 14 00:01:18 2016  commencing singleton removal, initial pass
Sun Aug 14 06:55:37 2016  memory use: 21024.0 MB
Sun Aug 14 06:55:38 2016  reading all ideals from disk
Sun Aug 14 07:07:31 2016  memory use: 33113.4 MB
Sun Aug 14 07:09:15 2016  keeping 678415747 ideals with weight <= 200, target excess is 4065047
Sun Aug 14 07:11:18 2016  commencing in-memory singleton removal
Sun Aug 14 07:12:24 2016  begin with 685540834 relations and 678415747 unique ideals
Sun Aug 14 07:26:27 2016  reduce to 468136203 relations and 440943184 ideals in 14 passes
Sun Aug 14 07:26:27 2016  max relations containing the same ideal: 168
Sun Aug 14 07:30:39 2016  removing 15689361 relations and 13689361 ideals in 2000000 cliques
Sun Aug 14 07:30:53 2016  commencing in-memory singleton removal
Sun Aug 14 07:31:34 2016  begin with 452446842 relations and 440943184 unique ideals
Sun Aug 14 07:38:12 2016  reduce to 452049659 relations and 426854194 ideals in 8 passes
Sun Aug 14 07:38:12 2016  max relations containing the same ideal: 162
Sun Aug 14 07:42:06 2016  removing 11892748 relations and 9892748 ideals in 2000000 cliques
Sun Aug 14 07:42:19 2016  commencing in-memory singleton removal
Sun Aug 14 07:43:00 2016  begin with 440156911 relations and 426854194 unique ideals
Sun Aug 14 07:49:43 2016  reduce to 439909808 relations and 416713073 ideals in 8 passes
Sun Aug 14 07:49:43 2016  max relations containing the same ideal: 160
Sun Aug 14 07:53:49 2016  removing 10693973 relations and 8693973 ideals in 2000000 cliques
Sun Aug 14 07:54:01 2016  commencing in-memory singleton removal
Sun Aug 14 07:54:41 2016  begin with 429215835 relations and 416713073 unique ideals
Sun Aug 14 08:01:05 2016  reduce to 429004964 relations and 407807247 ideals in 8 passes
Sun Aug 14 08:01:05 2016  max relations containing the same ideal: 159
Sun Aug 14 08:05:08 2016  removing 10012838 relations and 8012838 ideals in 2000000 cliques
Sun Aug 14 08:05:20 2016  commencing in-memory singleton removal
Sun Aug 14 08:06:03 2016  begin with 418992126 relations and 407807247 unique ideals
Sun Aug 14 08:10:46 2016  reduce to 418800944 relations and 399602322 ideals in 6 passes
Sun Aug 14 08:10:46 2016  max relations containing the same ideal: 157
Sun Aug 14 08:14:23 2016  removing 9564256 relations and 7564256 ideals in 2000000 cliques
Sun Aug 14 08:14:35 2016  commencing in-memory singleton removal
Sun Aug 14 08:15:14 2016  begin with 409236688 relations and 399602322 unique ideals
Sun Aug 14 08:20:44 2016  reduce to 409055837 relations and 391856374 ideals in 7 passes
Sun Aug 14 08:20:44 2016  max relations containing the same ideal: 154
Sun Aug 14 08:24:29 2016  removing 9246691 relations and 7246691 ideals in 2000000 cliques
Sun Aug 14 08:24:41 2016  commencing in-memory singleton removal
Sun Aug 14 08:25:20 2016  begin with 399809146 relations and 391856374 unique ideals
Sun Aug 14 08:29:45 2016  reduce to 399635501 relations and 384435222 ideals in 6 passes
Sun Aug 14 08:29:45 2016  max relations containing the same ideal: 153
Sun Aug 14 08:33:34 2016  removing 9006375 relations and 7006375 ideals in 2000000 cliques
Sun Aug 14 08:33:47 2016  commencing in-memory singleton removal
Sun Aug 14 08:34:26 2016  begin with 390629126 relations and 384435222 unique ideals
Sun Aug 14 08:39:07 2016  reduce to 390459882 relations and 377258828 ideals in 6 passes
Sun Aug 14 08:39:07 2016  max relations containing the same ideal: 153
Sun Aug 14 08:42:51 2016  removing 8821853 relations and 6821853 ideals in 2000000 cliques
Sun Aug 14 08:43:01 2016  commencing in-memory singleton removal
Sun Aug 14 08:43:37 2016  begin with 381638029 relations and 377258828 unique ideals
Sun Aug 14 08:49:33 2016  reduce to 381470513 relations and 370268688 ideals in 8 passes
Sun Aug 14 08:49:33 2016  max relations containing the same ideal: 151
Sun Aug 14 08:52:53 2016  removing 8681576 relations and 6681576 ideals in 2000000 cliques
Sun Aug 14 08:53:03 2016  commencing in-memory singleton removal
Sun Aug 14 08:53:37 2016  begin with 372788937 relations and 370268688 unique ideals
Sun Aug 14 08:58:49 2016  reduce to 372622013 relations and 363419433 ideals in 7 passes
Sun Aug 14 08:58:49 2016  max relations containing the same ideal: 148
Sun Aug 14 09:02:21 2016  removing 8571490 relations and 6571490 ideals in 2000000 cliques
Sun Aug 14 09:02:31 2016  commencing in-memory singleton removal
Sun Aug 14 09:03:06 2016  begin with 364050523 relations and 363419433 unique ideals
Sun Aug 14 09:08:00 2016  reduce to 363881749 relations and 356678357 ideals in 7 passes
Sun Aug 14 09:08:00 2016  max relations containing the same ideal: 147
Sun Aug 14 09:11:18 2016  removing 8493590 relations and 6493590 ideals in 2000000 cliques
Sun Aug 14 09:11:28 2016  commencing in-memory singleton removal
Sun Aug 14 09:11:58 2016  begin with 355388159 relations and 356678357 unique ideals
Sun Aug 14 09:16:44 2016  reduce to 355217009 relations and 350012803 ideals in 7 passes
Sun Aug 14 09:16:44 2016  max relations containing the same ideal: 142
Sun Aug 14 09:19:57 2016  removing 2562151 relations and 2073400 ideals in 488751 cliques
Sun Aug 14 09:20:05 2016  commencing in-memory singleton removal
Sun Aug 14 09:20:36 2016  begin with 352654858 relations and 350012803 unique ideals
Sun Aug 14 09:23:38 2016  reduce to 352640654 relations and 347925172 ideals in 5 passes
Sun Aug 14 09:23:38 2016  max relations containing the same ideal: 141
Sun Aug 14 09:25:33 2016  relations with 0 large ideals: 136690
Sun Aug 14 09:25:33 2016  relations with 1 large ideals: 64490
Sun Aug 14 09:25:33 2016  relations with 2 large ideals: 757752
Sun Aug 14 09:25:33 2016  relations with 3 large ideals: 4917692
Sun Aug 14 09:25:33 2016  relations with 4 large ideals: 19269157
Sun Aug 14 09:25:33 2016  relations with 5 large ideals: 48617583
Sun Aug 14 09:25:33 2016  relations with 6 large ideals: 80816161
Sun Aug 14 09:25:33 2016  relations with 7+ large ideals: 198061129
Sun Aug 14 09:25:33 2016  commencing 2-way merge
Sun Aug 14 09:30:29 2016  reduce to 250831685 relation sets and 246116203 unique ideals
Sun Aug 14 09:30:29 2016  commencing full merge
Sun Aug 14 11:54:44 2016  memory use: 27660.0 MB
Sun Aug 14 11:55:22 2016  found 108461347 cycles, need 108074403
Sun Aug 14 11:56:32 2016  weight of 108074403 cycles is about 14049712672 (130.00/cycle)
Sun Aug 14 11:56:32 2016  distribution of cycle lengths:
Sun Aug 14 11:56:32 2016  1 relations: 4686493
Sun Aug 14 11:56:32 2016  2 relations: 7212055
Sun Aug 14 11:56:32 2016  3 relations: 9083521
Sun Aug 14 11:56:32 2016  4 relations: 9297587
Sun Aug 14 11:56:32 2016  5 relations: 9297522
Sun Aug 14 11:56:32 2016  6 relations: 8858510
Sun Aug 14 11:56:32 2016  7 relations: 8237663
Sun Aug 14 11:56:32 2016  8 relations: 7553276
Sun Aug 14 11:56:32 2016  9 relations: 6809150
Sun Aug 14 11:56:32 2016  10+ relations: 37038626
Sun Aug 14 11:56:32 2016  heaviest cycle: 28 relations
Sun Aug 14 11:57:10 2016  commencing cycle optimization
Sun Aug 14 12:02:59 2016  start with 880784650 relations
Sun Aug 14 12:56:04 2016  pruned 40282237 relations
Sun Aug 14 12:56:07 2016  memory use: 23765.1 MB
Sun Aug 14 12:56:07 2016  distribution of cycle lengths:
Sun Aug 14 12:56:07 2016  1 relations: 4686493
Sun Aug 14 12:56:07 2016  2 relations: 7471500
Sun Aug 14 12:56:07 2016  3 relations: 9580536
Sun Aug 14 12:56:07 2016  4 relations: 9775419
Sun Aug 14 12:56:07 2016  5 relations: 9822771
Sun Aug 14 12:56:07 2016  6 relations: 9260070
Sun Aug 14 12:56:07 2016  7 relations: 8591686
Sun Aug 14 12:56:07 2016  8 relations: 7778534
Sun Aug 14 12:56:07 2016  9 relations: 6963407
Sun Aug 14 12:56:07 2016  10+ relations: 34143987
Sun Aug 14 12:56:07 2016  heaviest cycle: 28 relations
Sun Aug 14 13:03:08 2016  RelProcTime: 72542
Sun Aug 14 13:03:08 2016  elapsed time 20:09:07
Sun Aug 14 13:56:11 2016  
Sun Aug 14 13:56:11 2016  
Sun Aug 14 13:56:11 2016  Msieve v. 1.52 (SVN 946M)
Sun Aug 14 13:56:11 2016  random seeds: deae6b5c a4e55d09
Sun Aug 14 13:56:11 2016  factoring 2076257417856023699175915465047617492047417538914644293173543391581691848679845966461307599602751764750447990299840304521285406236817724619609422670858593468559717162885065034635636691512977714568402346477875599870907634691739715654867468282667550643309653973492548273536937869295166952423522011818026979 (304 digits)
Sun Aug 14 13:56:15 2016  no P-1/P+1/ECM available, skipping
Sun Aug 14 13:56:15 2016  commencing number field sieve (304-digit input)
Sun Aug 14 13:56:15 2016  R0: 2525116829404234886169433593750000000000000000000000000
Sun Aug 14 13:56:15 2016  R1: -2136272797135620621009768320282523261990381288068253749
Sun Aug 14 13:56:15 2016  A0: 150
Sun Aug 14 13:56:15 2016  A1: 0
Sun Aug 14 13:56:15 2016  A2: 0
Sun Aug 14 13:56:15 2016  A3: 0
Sun Aug 14 13:56:15 2016  A4: 0
Sun Aug 14 13:56:15 2016  A5: 0
Sun Aug 14 13:56:15 2016  A6: 1
Sun Aug 14 13:56:15 2016  skew 2.31, size 3.445e-16, alpha 1.379, combined = 2.315e-16 rroots = 0
Sun Aug 14 13:56:15 2016  
Sun Aug 14 13:56:15 2016  commencing linear algebra
Sun Aug 14 13:57:17 2016  read 108074403 cycles
Sun Aug 14 14:02:19 2016  cycles contain 350403919 unique relations
Sun Aug 14 18:55:40 2016  read 350403919 relations
Sun Aug 14 19:12:30 2016  using 20 quadratic characters above 4294917296
Sun Aug 14 19:48:04 2016  building initial matrix
Sun Aug 14 22:05:55 2016  memory use: 48373.3 MB
Sun Aug 14 22:25:13 2016  read 108074403 cycles
Sun Aug 14 22:25:40 2016  matrix is 108074226 x 108074403 (54471.9 MB) with weight 15385908232 (142.36/col)
Sun Aug 14 22:25:40 2016  sparse part has weight 13090662482 (121.13/col)
Sun Aug 14 23:13:08 2016  filtering completed in 2 passes
Sun Aug 14 23:13:43 2016  matrix is 108070616 x 108070793 (54471.6 MB) with weight 15385800295 (142.37/col)
Sun Aug 14 23:13:43 2016  sparse part has weight 13090630270 (121.13/col)
Mon Aug 15 00:03:27 2016  matrix starts at (0, 0)
Mon Aug 15 00:03:54 2016  matrix is 108070616 x 108070793 (54471.6 MB) with weight 15385800295 (142.37/col)
Mon Aug 15 00:03:54 2016  sparse part has weight 13090630270 (121.13/col)
Mon Aug 15 00:03:54 2016  saving the first 48 matrix rows for later
Mon Aug 15 00:04:27 2016  matrix includes 64 packed rows
Mon Aug 15 00:04:51 2016  matrix is 108070568 x 108070793 (52380.7 MB) with weight 13369678487 (123.71/col)
Mon Aug 15 00:04:51 2016  sparse part has weight 12650573991 (117.06/col)
Mon Aug 15 00:04:56 2016  using block size 8192 and superblock size 4423680 for processor cache size 46080 kB
Mon Aug 15 00:38:41 2016  commencing Lanczos iteration (48 threads)
Mon Aug 15 00:38:42 2016  memory use: 47963.0 MB
Mon Aug 15 00:45:24 2016  linear algebra at 0.0%, ETA 7574h 1m
Mon Aug 15 00:47:28 2016  checkpointing every 20000 dimensions

At current pace, it will finish next June. Ryan is currently attempting to sieve some additional relations and rerun filtering with TD=140.

Ryan appears to have prodigious sieving capacity, but in LA not so much.

Does anyone have any suggestions? Offers of help with LA? How high a value for TD should he attempt to reach, and will it help reduce ETA any appreciable amount?

TYIA.

WraithX · 2016-08-16, 12:10

Quote:

Originally Posted by swellman

Ryan Propper is attempting to factor C304_150_149, the granddaddy of the current xyyxf project. He ran ECM up to t65 with no factors appearing, selected the best SNFS poly via test sieving and has now sieved enough relations such that msieve builds a matrix and enters LA (@TD=130). Then the problems started...

At current pace, it will finish next June. Ryan is currently attempting to sieve some additional relations and rerun filtering with TD=140.

Ryan appears to have prodigious sieving capacity, but in LA not so much.

Does anyone have any suggestions? Offers of help with LA? How high a value for TD should he attempt to reach, and will it help reduce ETA any appreciable amount?

TYIA.

When I was working on HP49 S117 c210, I actually started the LA several times with various TD's to get an idea of the various matrix sizes and ETA's that would result. I bounced around on TD's, but I finally settled on 125 (I couldn't build with more than that), and trying 125 3 times gave me 3 different ETA's. I believe it was due to how the matrix was loaded into memory vs how the threads lined up on the processors. Here is the summary of the various TD's I tried:

Code:

TD 70 - ETA 4002h57m: matrix is 88382727 x 88382952 (25970.7 MB) with weight 6847042373 (77.47/col) sparse part has weight 5747458016 (65.03/col)
TD 80 - ETA 4640h 7m: matrix is 83909604 x 83909829 (27454.4 MB) with weight 7346597637 (87.55/col) sparse part has weight 6190094189 (73.77/col)
TD 85 - ETA 4513h 4m: matrix is 81992464 x 81992689 (28181.3 MB) with weight 7584940314 (92.51/col) sparse part has weight 6403641518 (78.10/col)
TD 90 - ETA 3602h20m: matrix is 80299721 x 80299946 (28917.8 MB) with weight 7824093700 (97.44/col) sparse part has weight 6617039915 (82.40/col)
TD 95 - ETA 3668h10m: matrix is 78767972 x 78768197 (29656.9 MB) with weight 8060707185 (102.33/col) sparse part has weight 6829171047 (86.70/col)
TD100 - ETA 4282h56m: matrix is 77349463 x 77349687 (30375.4 MB) with weight 8288226977 (107.15/col) sparse part has weight 7034545610 (90.94/col)
TD110 - ETA 3929h22m: matrix is 74870112 x 74870338 (31818.0 MB) with weight 8739992621 (116.74/col) sparse part has weight 7442460412 (99.40/col)
TD120 - ETA 3811h56m: matrix is 72742805 x 72743029 (33234.9 MB) with weight 9176491366 (126.15/col) sparse part has weight 7839402666 (107.77/col)
TD125 - ETA 3141h 6m: matrix is 71776154 x 71776379 (33924.4 MB) with weight 9386761820 (130.78/col) sparse part has weight 8031767895 (111.90/col)
TD125 - ETA 3750h36m: matrix is 71776154 x 71776379 (33924.4 MB) with weight 9386761820 (130.78/col) sparse part has weight 8031767895 (111.90/col)
TD125 - ETA 3054h11m: matrix is 71776154 x 71776379 (33924.4 MB) with weight 9386761820 (130.78/col) sparse part has weight 8031767895 (111.90/col)
TD128: Failed
TD130: Failed
TD150: Failed

I also only used 13, of 16, physical cores since more would reduce the runtime. My worst TD 125 was 3750hrs, my best was 3054hrs, so a savings of about 700 hours! It may be worth redoing the LA to see if you get a better ETA. You may be able to save at least a couple of months this way.

pinhodecarlos · 2016-08-16, 14:32

Maybe install MPI to take advantage of it while running msieve. Are his machines connected to each other through infiniband connection?

swellman · 2016-08-16, 14:35

WraithX - Nice data! Ryan has told me similar stories of varying ETA for the same TD. Hoping he weighs in here. It will be interesting to see what ETA he gets for TD=140.

swellman · 2016-08-16, 14:37

Quote:

Originally Posted by pinhodecarlos

Maybe install MPI to take advantage of it while running msieve.

Carlos - do you know anyone in the BOINC world with access to a MPI cluster who might be willing to help with the post processing of this monster?

pinhodecarlos · 2016-08-16, 14:39

Only Greg from NFS@Home but I suppose his grant ran out because he is not postprocessing the outstanding sieved numbers from the project.

frmky · 2016-08-16, 16:03

I do suggest continuing the sieving for a bit. I try to shoot for a minimum of 725 million unique relations and often continue to 800 million unique.

Second, on newer computers with multiple Intel processors it does noticeably help to use MPI to run one instance per processor and use threads to distribute within a processor, and hyperthreading does help. On a local machine with 2 cpus, each with 10 real cores, 20 virtual cores, I run using MPI with
-nc2 1,2 -t 20

pinhodecarlos · 2016-08-16, 16:03

Sean, do you know the size of the dat file?

frmky · 2016-08-16, 16:08

Quote:

Originally Posted by pinhodecarlos

Sean, do you know the size of the dat file?

It will be around 50-60 GB zipped.

Gimarel · 2016-08-18, 17:56

Try compiling msieve with -O2 instead of the default -O3. This should speed up LA a lot. At least on my machine for smaller jobs it's about 25% faster.

XYYXF · 2016-08-20, 13:13

Quote:

Originally Posted by swellman

Ryan Propper is attempting to factor C304_150_149, the granddaddy of the current xyyxf project. He ran ECM up to t65 with no factors appearing

t75 actually :)

2016-08-16, 14:32	#3
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 1353₁₆ Posts	Maybe install MPI to take advantage of it while running msieve. Are his machines connected to each other through infiniband connection? Last fiddled with by pinhodecarlos on 2016-08-16 at 14:36

2016-08-16, 14:35	#4
swellman Jun 2012 2²×13×59 Posts	WraithX - Nice data! Ryan has told me similar stories of varying ETA for the same TD. Hoping he weighs in here. It will be interesting to see what ETA he gets for TD=140. Last fiddled with by swellman on 2016-08-16 at 14:37

2016-08-16, 14:39	#6
pinhodecarlos "Carlos Pinho" Oct 2011 Milton Keynes, UK 3×17×97 Posts	Only Greg from NFS@Home but I suppose his grant ran out because he is not postprocessing the outstanding sieved numbers from the project.

2016-08-16, 16:03	#7
frmky Jul 2003 So Cal 100000111010₂ Posts	I do suggest continuing the sieving for a bit. I try to shoot for a minimum of 725 million unique relations and often continue to 800 million unique. Second, on newer computers with multiple Intel processors it does noticeably help to use MPI to run one instance per processor and use threads to distribute within a processor, and hyperthreading does help. On a local machine with 2 cpus, each with 10 real cores, 20 virtual cores, I run using MPI with -nc2 1,2 -t 20

2016-08-18, 17:56	#10
Gimarel Apr 2010 2·83 Posts	Try compiling msieve with -O2 instead of the default -O3. This should speed up LA a lot. At least on my machine for smaller jobs it's about 25% faster.