A large project for the new year

[fivemack]

Originally Posted by Andi47

OK, I will keep -e 4.5e-13. If you want, I can mail the zipped .cand files to you as soon as they are finished. (currently pol51opt is at ~70% for 11-12M and at ~11% for 10-11M, doing these ranges on two different nodes.)

Sending them would be kind, thanks. They really shouldn't be that long: I'm not getting more than 100k uncompressed per million searched.

P.S.: You should obscure your mail address to avoid massive spam (spambots)

I have spam-filtering at a level that I'm reasonably happy with; I quite like leaving my mail address transparently visible, it seems like a gentlemanly throwback to a more civilised age.

[Andi47]

Originally Posted by fivemack

Sending them would be kind, thanks. They really shouldn't be that long: I'm not getting more than 100k uncompressed per million searched.

My .cand file is ~73% through the range of 11M-12M and it is ~361k uncompressed until now. This range seems to be quite productive.

[smh]

Originally Posted by Andi47

My .cand file is ~73% through the range of 11M-12M and it is ~361k uncompressed until now. This range seems to be quite productive.

100K per million seems a bit low. I have about 1.25M for a 2 million range.

[jbristow]

I'm 60% through my 1M range and my filesize is 85KB, but I set my threshold at 4.8e-13 instead of 4.5e-13.

[fivemack]

I've just got round to rebuilding the matrix for a medium-sized (700-bit) SNFS job for various settings of TARGET_DENSITY to see what happens. The figure-of-merit must be matrix size * number of set bits in sparse part.

Weight 65:
   weight of 3985391 cycles is about 259231780 (65.05/cycle)
   matrix is 3940580 x 3940827 with weight 273210040 (avg 69.33/col)
   s*d = 1076673502303080
Weight 96:
   weight of 3427391 cycles is about 329063241 (96.01/cycle)
   matrix is 3411487 x 3411735 with weight 336713217 (avg 98.69/col)
   s*d = 1148776267401495
Weight 128: 
   weight of 3119391 cycles is about 399921231 (128.20/cycle)
   matrix is 3114577 x 3114825 with weight 396321119 (avg 127.24/col)
   s*d = 1234470929489175

With TARGET_DENSITY set to 32 or 48, following your suggestion that 65 might be even a bit larger than optimal, I get an endless set of 'matrix not dense enough; retrying' messages followed by a crash.

19:32:11 fivemack@kolmogorov:/home/nfsworld/7+366b$  ~/maths/tools/msieve-1.32/msieve -v -a 48 -nc


Msieve v. 1.32
Sun Jan  6 19:32:19 2008
random seeds: 0c1d776e eb605301
factoring 4123017239829960655360724341694621497464612147710415876665657414658658924822579892563172788470173781858953283741390375209876161708084158357838108434241 (151 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (151-digit input)
R0: -44567640326363195900190045974568007
R1:  1
A0:  49
A1:  0
A2:  0
A3: -7
A4:  0
A5:  0
A6:  1
size score = 3.744454e-10, Murphy alpha = 0.806201, combined = 2.974073e-10
restarting with 30632263 relations

commencing relation filtering
commencing duplicate removal, pass 1
error -15 reading relation 24370638
found 8036577 hash collisions in 30632262 relations
commencing duplicate removal, pass 2
found 7027903 duplicates and 23604359 unique relations
memory use: 153.2 MB
ignoring smallest 1045124 rational and 1045055 algebraic ideals
filtering ideals above 16233126
need 3553304 more relations than ideals
commencing singleton removal, pass 1
relations with 0 large ideals: 74277
relations with 1 large ideals: 703240
relations with 2 large ideals: 3495102
relations with 3 large ideals: 7683567
relations with 4 large ideals: 8076267
relations with 5 large ideals: 3571906
relations with 6 large ideals: 0
relations with 7+ large ideals: 0
23604359 relations and about 20330794 large ideals
commencing singleton removal, pass 2
found 6130615 singletons
current dataset: 17473744 relations and about 13470319 large ideals
commencing singleton removal, pass 3
found 1297014 singletons
current dataset: 16176730 relations and about 12133087 large ideals
commencing singleton removal, pass 4
found 277710 singletons
current dataset: 15899020 relations and about 11853230 large ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 15899020 relations and 13229189 unique ideals
reduce to 13959672 relations and 11238803 ideals in 12 passes
max relations containing the same ideal: 28
dataset has 30.2% excess relations
ignoring smallest 947130 rational and 947336 algebraic ideals
filtering ideals above 14609813
need 2448782 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 15899020 relations and 13424866 unique ideals
reduce to 13958597 relations and 11433370 ideals in 12 passes
max relations containing the same ideal: 29
removing 377171 relations and 338949 ideals in 38222 cliques
commencing in-memory singleton removal
begin with 13581426 relations and 11433370 unique ideals
reduce to 13575552 relations and 11088527 ideals in 6 passes
max relations containing the same ideal: 27
removing 281769 relations and 243547 ideals in 38222 cliques
commencing in-memory singleton removal
begin with 13293783 relations and 11088527 unique ideals
reduce to 13290294 relations and 10841479 ideals in 6 passes
max relations containing the same ideal: 27
dataset has 17.2% excess relations
ignoring smallest 848404 rational and 848063 algebraic ideals
filtering ideals above 12986500
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 545.0 MB
commencing in-memory singleton removal
begin with 13290294 relations and 11039468 unique ideals
reduce to 13290148 relations and 11039322 ideals in 5 passes
max relations containing the same ideal: 29
dataset has 7.7% excess relations
relations with 0 large ideals: 47123
relations with 1 large ideals: 412417
relations with 2 large ideals: 2043754
relations with 3 large ideals: 4269401
relations with 4 large ideals: 4289498
relations with 5 large ideals: 1989734
relations with 6 large ideals: 220505
relations with 7+ large ideals: 17716
commencing 2-way merge
reduce to 9168017 relation sets and 6917191 unique ideals
commencing full merge
found 5109342 cycles, need 4555391
weight of 4555391 cycles is about 218820519 (48.04/cycle)
distribution of cycle lengths:
1 relations: 708625
2 relations: 853851
3 relations: 819210
4 relations: 668116
5 relations: 519251
6 relations: 394302
7 relations: 297024
8 relations: 214043
9 relations: 80475
10+ relations: 494
heaviest cycle: 10 relations
matrix not dense enough, retrying
dataset has 7.7% excess relations
ignoring smallest 748882 rational and 748589 algebraic ideals
filtering ideals above 11363188
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 545.0 MB
commencing in-memory singleton removal
begin with 13290294 relations and 11238460 unique ideals
reduce to 13290081 relations and 11238247 ideals in 5 passes
max relations containing the same ideal: 30
dataset has -1.8% excess relations
relations with 0 large ideals: 41605
relations with 1 large ideals: 319502
relations with 2 large ideals: 1721730
relations with 3 large ideals: 3916948
relations with 4 large ideals: 4384099
relations with 5 large ideals: 2389693
relations with 6 large ideals: 460347
relations with 7+ large ideals: 56157
commencing 2-way merge
reduce to 9167791 relation sets and 7115957 unique ideals
commencing full merge
found 5108113 cycles, need 4554157
weight of 4554157 cycles is about 218622101 (48.00/cycle)
distribution of cycle lengths:
1 relations: 694837
2 relations: 862146
3 relations: 824241
4 relations: 670573
5 relations: 519946
6 relations: 394147
7 relations: 296301
8 relations: 212965
9 relations: 78269
10+ relations: 732
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -1.8% excess relations
ignoring smallest 648541 rational and 647786 algebraic ideals
filtering ideals above 9739875
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 545.0 MB
commencing in-memory singleton removal
begin with 13290294 relations and 11439603 unique ideals
reduce to 13290063 relations and 11439372 ideals in 5 passes
max relations containing the same ideal: 35
dataset has -11.5% excess relations
relations with 0 large ideals: 35953
relations with 1 large ideals: 236392
relations with 2 large ideals: 1400295
relations with 3 large ideals: 3501084
relations with 4 large ideals: 4398344
relations with 5 large ideals: 2810299
relations with 6 large ideals: 774533
relations with 7+ large ideals: 133163
commencing 2-way merge
reduce to 9167719 relation sets and 7317028 unique ideals
commencing full merge
found 5107195 cycles, need 4553228
weight of 4553228 cycles is about 218620412 (48.01/cycle)
distribution of cycle lengths:
1 relations: 682345
2 relations: 866082
3 relations: 827649
4 relations: 673006
5 relations: 522281
6 relations: 394658
7 relations: 297000
8 relations: 213344
9 relations: 75863
10+ relations: 1000
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -11.5% excess relations
ignoring smallest 547061 rational and 546683 algebraic ideals
filtering ideals above 8116563
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 13290294 relations and 11642186 unique ideals
reduce to 13290058 relations and 11641950 ideals in 5 passes
max relations containing the same ideal: 38
dataset has -21.1% excess relations
relations with 0 large ideals: 30381
relations with 1 large ideals: 164281
relations with 2 large ideals: 1083591
relations with 3 large ideals: 3019397
relations with 4 large ideals: 4297082
relations with 5 large ideals: 3237144
relations with 6 large ideals: 1182040
relations with 7+ large ideals: 276142
commencing 2-way merge
reduce to 9167700 relation sets and 7519592 unique ideals
commencing full merge
found 5107763 cycles, need 4553792
weight of 4553792 cycles is about 218642801 (48.01/cycle)
distribution of cycle lengths:
1 relations: 675407
2 relations: 865782
3 relations: 829953
4 relations: 675349
5 relations: 525324
6 relations: 396478
7 relations: 297199
8 relations: 213741
9 relations: 73362
10+ relations: 1197
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -21.1% excess relations
ignoring smallest 444325 rational and 443978 algebraic ideals
filtering ideals above 6493250
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 13290294 relations and 11847627 unique ideals
reduce to 13290058 relations and 11847391 ideals in 5 passes
max relations containing the same ideal: 44
dataset has -31.0% excess relations
relations with 0 large ideals: 24669
relations with 1 large ideals: 103958
relations with 2 large ideals: 777388
relations with 3 large ideals: 2459595
relations with 4 large ideals: 4042356
relations with 5 large ideals: 3628358
relations with 6 large ideals: 1711328
relations with 7+ large ideals: 542406
commencing 2-way merge
reduce to 9167699 relation sets and 7725032 unique ideals
commencing full merge
found 5105204 cycles, need 4551232
weight of 4551232 cycles is about 218662962 (48.04/cycle)
distribution of cycle lengths:
1 relations: 667520
2 relations: 865959
3 relations: 831184
4 relations: 675727
5 relations: 526141
6 relations: 397062
7 relations: 297506
8 relations: 213994
9 relations: 74576
10+ relations: 1563
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -31.0% excess relations
ignoring smallest 340005 rational and 339863 algebraic ideals
filtering ideals above 4869937
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 13290294 relations and 12056062 unique ideals
reduce to 13290058 relations and 12055826 ideals in 5 passes
max relations containing the same ideal: 49
dataset has -41.0% excess relations
relations with 0 large ideals: 18891
relations with 1 large ideals: 56318
relations with 2 large ideals: 492417
relations with 3 large ideals: 1825875
relations with 4 large ideals: 3564199
relations with 5 large ideals: 3906358
relations with 6 large ideals: 2379722
relations with 7+ large ideals: 1046278
commencing 2-way merge
reduce to 9167699 relation sets and 7933467 unique ideals
commencing full merge
found 5105654 cycles, need 4551667
weight of 4551667 cycles is about 218575752 (48.02/cycle)
distribution of cycle lengths:
1 relations: 663984
2 relations: 867146
3 relations: 833513
4 relations: 676518
5 relations: 526549
6 relations: 398245
7 relations: 297517
8 relations: 212804
9 relations: 73725
10+ relations: 1666
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -41.0% excess relations
ignoring smallest 233356 rational and 233306 algebraic ideals
filtering ideals above 3246625
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 13290294 relations and 12269268 unique ideals
reduce to 13290058 relations and 12269032 ideals in 5 passes
max relations containing the same ideal: 62
dataset has -51.2% excess relations
relations with 0 large ideals: 12947
relations with 1 large ideals: 22877
relations with 2 large ideals: 245276
relations with 3 large ideals: 1125466
relations with 4 large ideals: 2756013
relations with 5 large ideals: 3879374
relations with 6 large ideals: 3172311
relations with 7+ large ideals: 2075794
commencing 2-way merge
reduce to 9167699 relation sets and 8146673 unique ideals
commencing full merge
found 5104853 cycles, need 4550873
weight of 4550873 cycles is about 218522905 (48.02/cycle)
distribution of cycle lengths:
1 relations: 662818
2 relations: 866482
3 relations: 834215
4 relations: 677830
5 relations: 526920
6 relations: 398432
7 relations: 297847
8 relations: 212581
9 relations: 72139
10+ relations: 1609
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -51.2% excess relations
ignoring smallest 122775 rational and 122531 algebraic ideals
filtering ideals above 1623312
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 666.1 MB
commencing in-memory singleton removal
begin with 13290294 relations and 12490624 unique ideals
reduce to 13290058 relations and 12490388 ideals in 5 passes
max relations containing the same ideal: 99
dataset has -61.7% excess relations
relations with 0 large ideals: 6779
relations with 1 large ideals: 4302
relations with 2 large ideals: 64055
relations with 3 large ideals: 416595
relations with 4 large ideals: 1463031
relations with 5 large ideals: 3018167
relations with 6 large ideals: 3754403
relations with 7+ large ideals: 4562726
commencing 2-way merge
reduce to 9167699 relation sets and 8368029 unique ideals
commencing full merge
found 5102215 cycles, need 4548229
weight of 4548229 cycles is about 218512584 (48.04/cycle)
distribution of cycle lengths:
1 relations: 660768
2 relations: 865271
3 relations: 834577
4 relations: 677757
5 relations: 526976
6 relations: 398019
7 relations: 298269
8 relations: 213061
9 relations: 71922
10+ relations: 1609
heaviest cycle: 11 relations
matrix not dense enough, retrying
dataset has -61.7% excess relations
ignoring smallest 0 rational and 0 algebraic ideals
filtering ideals above 0
need 2257393 more relations than ideals
commencing singleton removal, final pass
memory use: 1405.0 MB
commencing in-memory singleton removal
begin with 13290294 relations and 12735930 unique ideals
reduce to 13290058 relations and 12735694 ideals in 5 passes
max relations containing the same ideal: 13236213
dataset has -73.5% excess relations
relations with 0 large ideals: 0
relations with 1 large ideals: 0
relations with 2 large ideals: 0
relations with 3 large ideals: 0
relations with 4 large ideals: 0
relations with 5 large ideals: 0
relations with 6 large ideals: 0
relations with 7+ large ideals: 13290058
commencing 2-way merge
reduce to 9167699 relation sets and 8613335 unique ideals
commencing full merge
failed to reallocate 0 bytes

[Jay]

memory use: 1405.0 MB

That's mighty close to 2gb. By the time you add in the size of the binary and misc variables, I'll bet you're bumping up against the limit.

[jasonp]

Originally Posted by fivemack

I've just got round to rebuilding the matrix for a medium-sized (700-bit) SNFS job for various settings of TARGET_DENSITY to see what happens. The figure-of-merit must be matrix size * number of set bits in sparse part.

Almost true; when filtering starts, each relation remembers how many factors it has that are below the filtering bound. There's no way to track whether these factors increase or decrease as merges happen, and the code assumes that matrix entries corresponding to these primes never cancel because of fortuitous merges. Merges that cancel out a relation within a relation set are assumed to remove a fixed number of these untracked factors. Factors less than 100 are not counted at all in these totals, since merges can change them arbitrarily and they obscure the behavior of the larger untracked primes. So basically the code tracks primes above the filtering bound exactly and primes below the bound approximately. The figure of merit is the number of estimated nonzeros in the lightest few cycles divided by the number of required matrix columns; the former are tracked in a hashtable as merging progresses.

The 'matrix is AAA x BBB...' messages are from the linear algebra, which tracks all ideals exactly. This will start off much larger than what the filtering saw because the small primes and quadratic characters are added in, then a bunch are removed so the weight per column drops to a bit more than the filtering estimated

With TARGET_DENSITY set to 32 or 48, following your suggestion that 65 might be even a bit larger than optimal, I get an endless set of 'matrix not dense enough; retrying' messages followed by a crash.

Code at the bottom of gnfs/filter/filter.c reruns the merge phase with a 10% smaller filtering bound whenever the average number of nonzeros per column is below 60.0, independent of the choice of TARGET_DENSITY. Obviously you can't rerun the merge phase more than 10 times under these circumstances :) v1.33 will complain and exit before that happens. These measures were instated due to trouble described here.

Jay, Tom doesn't bother with 32-bit machines :)

[Jay]

Originally Posted by jasonp

Jay, Tom doesn't bother with 32-bit machines :)

You mean some people don't use Billy Boy's Window machines?

I tried looking back through the posts to see what he was running under, but didn't see any mention. So thought I'd mention it on the off chance that it played a role in the problem. Am glad to hear that it isn't the problem.

[xilman]

Originally Posted by Jay

You mean some people don't use Billy Boy's Window machines?

I tried looking back through the posts to see what he was running under, but didn't see any mention. So thought I'd mention it on the off chance that it played a role in the problem. Am glad to hear that it isn't the problem.

64-bit Windows has been available for years. Many years, in the case of NT for Alpha.


Paul