C304_150_149
 

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
[/code]

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.

[QUOTE=swellman;440100]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.[/QUOTE]
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
[/CODE]
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. :smile:

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

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.

[QUOTE=pinhodecarlos;440112]Maybe install MPI to take advantage of it while running msieve.[/QUOTE]

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?

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

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

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

[QUOTE=pinhodecarlos;440119]Sean, do you know the size of the dat file?[/QUOTE]

It will be around 50-60 GB zipped.

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.

[QUOTE=swellman;440100]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[/QUOTE]t75 actually :)

Many thanks to all for the helpful tips. Ryan has implemented them and has made progress. He is currently attempting to sieve additional uniques and incrementing TD to find the "sweet spot" wrt ETA. I'm not sure there's anything sweet about this monster but he's engaged it. I'm just hoping he can get an ETA under 4000 hours but who knows? I'll report his progress as things er progress.

Update: LA is in full swing with an ETA of -4800 hours (early May). :ermm:

150^149+149^150 has been factored. The mighty giant lies slain.

Ryan ran the sieving, Greg Childers the LA/postprocessing. It was a great effort and personally I am in awe of their accomplishment.

[code]
p112=4589717414070503932356610139809713246293714200289874762254641434246464550705097961311966128119332304236622320109
p192=452371514527436596669656271361055896200135049572909801471049275612551239658558845331878122140222413088563004287778808937264541956636576326085349433639397620869454531909234048542341368429340431
[/code]

[QUOTE=swellman;456367]150^149+149^150 has been factored. The mighty giant lies slain.

Ryan ran the sieving, Greg Childers the LA/postprocessing. It was a great effort and personally I am in awe of their accomplishment.

[code]
p112=4589717414070503932356610139809713246293714200289874762254641434246464550705097961311966128119332304236622320109
p192=452371514527436596669656271361055896200135049572909801471049275612551239658558845331878122140222413088563004287778808937264541956636576326085349433639397620869454531909234048542341368429340431
[/code][/QUOTE]Very nice!

Here's the msieve log file for the number:

[PASTEBIN]2yVGizNd[/PASTEBIN]

Most impressive! Kudos!

... This factorization (a 326-digit SNFS difficulty, a clear record peak for quite some time to stay*) is probably a good reason to get [URL="http://www.primefan.ru/xyyxf/default.html"]all XYYXF webpages[/URL] refereshed?

The latest update is date-stamped on Jan.4.
_________________
*and not likely to be beaten before current XYYXF pages are extended some day (from 150 to 200, like they were extended when all numbers y<x<=100 were almost finished).

Am I correct in thinking that that was 16x24 threads?

I assume that raising the lp bound would only make the matrix harder. Are the msieve problems fixed with large datasets?

Nice record. Can't wait for it to be beaten.

Yes, the linear algebra was completed on 16 compute nodes, each with a Xeon E5-2650 v4 cpu with DDR4 memory connected by FDR Infiniband. This cpu has 12 cores with hyperthreading, so 24 msieve threads per node.

The actual Infiniband data transfer rate during the computation was about 700 MB/s in each direction on each node as measured by the HCA counters.

[QUOTE=Batalov;456427]... This factorization (a 326-digit SNFS difficulty, a clear record peak for quite some time to stay*) is probably a good reason to get [URL="http://www.primefan.ru/xyyxf/default.html"]all XYYXF webpages[/URL] refereshed?

The latest update is date-stamped on Jan.4.[/QUOTE]You are right!
Going to update them in a day or two.