A large project for the new year
 

I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.

I think all the pieces for this exist: RSA-200 proved that polynomial selection by Kleinjung's code is reasonable up to 200 digits and sieving with the Franke siever demonstrably works that far; msieve is likely to filter and run in reasonable (a quad-core month or so) time provided that the matrix fits in 8GB or so.

Aoki's team has produced matrices of that sort of size for even 176-digit numbers, though I suspect they have at least one filtering technique better than msieve currently offers - their matrices are much smaller and denser than I get by extrapolating from the medium GNFS jobs I've run with msieve. They used parallel linear algebra, but didn't have access to 8GB machines at the time. They also used parallel filtering; filtering takes a bit more memory than the matrix step, but is apparently local enough that it can be allowed to run on fast swap disc.

To get the sieving done in reasonable time will require a few dozen cores, which means I will have to get several people to help, which means it makes sense to ask around for an appropriate number rather than pick one.

I don't see anything obvious on the more-wanted list or the first-five-holes tables: anything with few enough digits is also of small enough SNFS difficulty that you'd use that instead, though the decision is perhaps not absolutely clear for 10^232+1.

My preferred candidate is the cofactor of 6^383+1. It's 165 digits, so would be a second-champion; it has a prime exponent; it has the largest ratio of SNFS difficulty to digit count of any number in the tables.

If that's too far to stretch, there is clearly already interest in 3^527-1 C160/S252, though I'd not want to set up to shoot that fox if akruppa is already ready to hunt it.

If people are not interested in this, I'll return to picking off Cunningham-table entries in order by SNFS difficulty ...

I'm willing to donate my 2.4 GHz quad-core but it only has 2GB of memory. Of course I can easily add more memory but the main issue here is my lack of knowledge on how to run msieve and the rest of the software. I have to study them...the offer stands...

Carlos

It's not much, but I can offer one core of an Athlon X2 4400+ for lattice sieving. I already have GGNFS up and running via Msys.

[QUOTE=fivemack;120330]I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.

...[/QUOTE]

How big is "noticeably greater"? 160 digits? 170? 180?

Perhaps you might try one of the following:

12,253+ C169. (via SNFS it is C249)
2,1105- C158 (SNFS is bad via 4th degree)
11,266+ C165
2,1598M C160 (slightly easier than with SNFS)
10,232+ C160
2,832+ C175
2,980+ C162 (definitely easier than SNFS)
2,1012+ C163 ditto.
M827 C172


or really ambitious,

2,1157- c182 etc.

I can suggest some others.

[QUOTE=fivemack;120330]I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.


Aoki's team has produced matrices of that sort of size for even 176-digit numbers, though I suspect they have at least one filtering technique better than msieve currently offers ...[/QUOTE]

I have my own (very old) filter code; It is witten in Fortran, dates from
1990, and uses intelligent Gaussian elimination. It produces very poor
matrices.

For this reason, I use the CWI filter code. It seems to produce much
better matrices than what I have seen reported by others.

@fivemack: I suspect Aoki's team uses lattice sieving with composite special-q, in order to avoid a proliferation of large primes that must be dealt with during filtering. Franke has a presentation somewhere that shows the technique produces smaller but denser matrices.

@Bob: comparing the CWI filtering with msieve's filtering is something I'm always interested in. The only head-to-head comparison using the same set of relations, that I've been able to find ([url="http://mersenneforum.org/showpost.php?p=115343&postcount=12"]for 5,323-[/url]), puts the two packages on the same curve of size-vs-density. The CWI matrix was about 10% smaller and about 10% more dense than the msieve version. Do you have additional figures?

Such a large GNFS job is going to be a severe test of msieve's square root. I need to do some work to flush intermediate numbers to disk, in order to allow bigger FFTs, but that's not very involved and it would certainly be done by the time it was needed.

[QUOTE=fivemack;120330]I am interested, in 2008, in performing a GNFS factorisation of size noticeably greater than 512 bits.[/QUOTE]I can (very probably) persuade the CWI filtering code to do a good job on a collection of relaions iff:

1) no large prime is > 1e9
2) routines to convert into and out of CWI format are available.

I can possibly provide 2) if they are not already written.

I've about 10 years experience with the CWI code and can generally get a reasonable matrix from some relations. Doing so is much more an art, or possibly a craft, than a science.

FWIW, I just started a 516-bit GNFS (of 2,1574L) on my home machines. It should be finished by April, and possibly earlier if I can persuade a lattice siever to run on my wife's Vista machine at rather more than 1% of the performance of my Linux box.


Paul

[QUOTE=jasonp;120359@Bob: comparing the CWI filtering with msieve's filtering is something I'm always interested in. The only head-to-head comparison using the same set of relations, that I've been able to find ([url="http://mersenneforum.org/showpost.php?p=115343&postcount=12"]for 5,323-[/url]), puts the two packages on the same curve of size-vs-density. The CWI matrix was about 10% smaller and about 10% more dense than the msieve version. Do you have additional figures?

QUOTE]

I have my own code, so I have not installed msieve. If you like,
I can gather together all my relations for my current project (6,299-)
and send them to you (on CD; via snail mail). Then we can compare
results. 6,299- should finish sieving in 2-3 days. [it would be done
already if a server hadn't gone down last weekend].

[QUOTE=R.D. Silverman;120371]
I have my own code, so I have not installed msieve. If you like,
I can gather together all my relations for my current project (6,299-)
and send them to you (on CD; via snail mail). Then we can compare
results. 6,299- should finish sieving in 2-3 days.[/QUOTE]
That would be a good idea; I'll send my snail-mail address via email.

PS: In my previous post I meant 5,317-

[QUOTE=R.D. Silverman;120350]How big is "noticeably greater"? 160 digits? 170? 180?[/QUOTE]

I was thinking somewhere around 165 - big enough to be second-champion for Cunningham GNFS, but small enough that I can reasonably extrapolate the runtime, that the polynomial search doesn't itself require substantial multi-contributor logistics, and hopefully that people can use the ggnfs Windows builds of gnfs-lasieve4I14e rather than having to fiddle around with cross-compilers to get a gnfs-lasieve4I15e Windows binary: I have no Windows machine at the moment.

My prejudice is to have a prime exponent and a large SNFS-to-GNFS ratio, which makes 6^383+1 perfect, though I realise it's a long way beyond the smallest holes, and that six isn't prime so I can't claim to be contributing to knowledge about the structure of finite fields.

[QUOTE]
Perhaps you might try one of the following:

12,253+ C169. (via SNFS it is C249)
2,1105- C158 (SNFS is bad via 4th degree)
11,266+ C165
2,1598M C160 (slightly easier than with SNFS)
10,232+ C160
2,832+ C175
2,980+ C162 (definitely easier than SNFS)
2,1012+ C163 ditto.
M827 C172
[/QUOTE]

That's quite a long list, and I don't quite see the rationale behind its entries; there's one more-wanted, a few early holes, but I'm wondering why something like 2,1012+ is on the list when something like 5,391- (C161, S273) isn't. I presume a factor of 17 in the exponent is useless, and even if you could multiply the difficulty by 16/17 somehow it would still be S258 and easier by GNFS.

[QUOTE=jasonp;120359]@fivemack: I suspect Aoki's team uses lattice sieving with composite special-q, in order to avoid a proliferation of large primes that must be dealt with during filtering. Franke has a presentation somewhere that shows the technique produces smaller but denser matrices.[/QUOTE]

I'm not sure that's compatible with (from the Aoki report [url]http://www.loria.fr/~zimmerma/records/11_281+[/url] )

[CODE]
special-Q: only for algebraic side.
100% of 30.5M-221.2M except 111.5M-113.4M (about 10.2M ideals)
83% of 28.8M-30.5M, 221.2M-227.0M (about 0.3M)
[/CODE]

where pi(221M) - pi(30.5M) is about ten million.

My suspicion is that this is simply significant over-sieving; they use 576M relations where, for LP=2^32, I would have expected to need about 350M to make a barely-adequate matrix.

I don't know what the asymptotics of over-sieving are like: I did one, accidental experiment ([url]http://www.mersenneforum.org/showthread.php?t=9381[/url]) in which 26M relations gave no matrix, 27M relations gave a matrix with side 2746454 and cycle-entries 178617306, and 34M gave side 2261961, cycle-entries 147036684, so the weight per row stayed absolutely constant and the side is going down. But I don't know if the conclusion to draw is '7 million relations reduce the side by 20%' or '25% more relations than needed for a minimal matrix reduce the side by 20%', and I don't know whether going further would make the weight per row start to go up.

I suppose I could deliberately grotesquely over-sieve some number, but I don't understand the underlying process enough to know whether results for lp=2^26 will scale to a run with lp=2^31 or whether results for SNFS will be transferrable to GNFS, and I don't particularly want to spend the CPU time to sieve a complete-after-1000-hours problem for a thousand more hours.

[QUOTE=fivemack;120397]
I don't know what the asymptotics of over-sieving are like: I did one, accidental experiment ([url]http://www.mersenneforum.org/showthread.php?t=9381[/url]) in which 26M relations gave no matrix, 27M relations gave a matrix with side 2746454 and cycle-entries 178617306, and 34M gave side 2261961, cycle-entries 147036684, so the weight per row stayed absolutely constant and the side is going down. But I don't know if the conclusion to draw is '7 million relations reduce the side by 20%' or '25% more relations than needed for a minimal matrix reduce the side by 20%', and I don't know whether going further would make the weight per row start to go up.
[/QUOTE]
In general, the filtering produces a continuum of matrices, some larger and less dense, others smaller and more dense. The only real requirements are that the final number of matrix columns be a little larger than the number of rows, and that the number of columns must be at least the number of factor base entries ignored by the filtering. Smaller matrices reduce the block lanczos overhead but increase the matrix multiply time; given feedback about how long each part takes it's possible to pick a matrix out of all the possibilities that minimizes the solve time.

Msieve takes a very basic approach: the literature has matrices that average 60-70 nonzeros per column, so the filtering will first produce a collection of matrix columns that meets the minimum requirements for a usable matrix, then squeezes that down by continuing to merge ideals until the estimated average number of nonzeros in the lightest matrix columns found exceeds TARGET_DENSITY (=65.0). Just increasing this number will produce smaller matrices that are more dense; however, the few timing experiments I've done indicate that 65.0 is already a little too high, in that larger but sparser matrices solve slightly faster. So it makes sense that the density stays the same as you oversieve but the size goes down...it's that way by design :)

Having heard that the CWI filtering tools require some experience combined with trial-and-error in order to do a good job, I set out to make my filtering try to do a good job automatically. I think it does a good enough job now, but don't really know how much better it can be made to perform.

The NFSNET factorizations I've seen so far are pretty significantly oversieved, with enough excess so that clique processing gets rid of a large number (~40%) of the relations that survive the singleton removal.

[QUOTE=fivemack;120330]To get the sieving done in reasonable time will require a few dozen cores, which means I will have to get several people to help[/QUOTE]I can spare a couple of cpu's for this

OK, let's hunt polynomials
 

I assume you have the executable pol51m0b available; it's part of the ggnfs package.

Create a file called '6.383.data' containing the single line

[code]
N 230380135646168002240144238096238189782429580465812519176892278271650463794969643225877877269156894108094881082195219664775471894182470295616143804362949333632033489
[/code]

Pick a5 ranges among yourselves; a quarter-million a5 will take, I think, a CPU-day on a 2.5GHz machine to sieve and about a CPU-week to optimise, and produce around 100MB of output.

For example, if you've picked the range 1.75 to 2 million, do
[code]
ggnfs/bin/pol51m0b -p 8 -n 1e25 -b 6.383 -a 1750000 -A 2000000
[/code]

If you have to stop the job half-way through, simply look at the last line in the file 6.383.51.m that it creates, which will be of the form
[code]
1802134060 6819433011508008067 31019844821582516560648299688392
[/code]
and start again with -a 1802134 - that is, the first number in the last line divided by 1000.

After that job has completed, and created a file 6.383.51.m, run

[code]
ggnfs/bin/pol51opt -b 6.383 -n 1.5e23 -N 6e20 -e 4.5e-13
[/code]

which will take rather longer to run, and will create a (hopefully fairly small) file 6.383.cand.

Find the line in that file of the form
[code]
BEGIN POLY #skewness 1018899.74 norm 4.05e+22 alpha -5.02 Murphy_E 5.03e-13
[/code]

with the largest Murphy_E number at the end, and post here the section from that 'BEGIN POLY' line to the 'END POLY' line which follows.

Sorry if I'm teaching people to suck eggs here.

We probably want to search for a total of around half a GHz-year, IE up to about a5=6000000 - the best polynomial I've found in a very small search would take about five GHz-years to sieve.

I'll run a=0 through 250000.

[quote=fivemack;120394]
That's quite a long list, and I don't quite see the rationale behind its entries; there's one more-wanted, a few early holes, but I'm wondering why [/QUOTE]

What makes you think there is a rationale? I simply consulted the Tarot....
There is a bias toward base 2.

[QUOTE=fivemack;120421]
Pick a5 ranges among yourselves; a quarter-million a5 will take, I think, a CPU-day on a 2.5GHz machine to sieve and about a CPU-week to optimise, and produce around 100MB of output.
[/QUOTE]

Those timings are, to use a technical term, balderdash; a better estimate is 1000 a5 sieved per CPU-minute, say rather over a million a day. So we can aim to do a5 up to at least 25 million, and it would make more sense to reserve in blocks of 10^6. I'll take 0-1000000.

[QUOTE=fivemack;120330]
If that's too far to stretch, there is clearly already interest in 3^527-1 C160/S252, though I'd not want to set up to shoot that fox if akruppa is already ready to hunt it.[/QUOTE]

I have no plans for this number.


Edit:
[QUOTE="Paul Leyland"]
1) no large prime is > 1e9
[/QUOTE]

I used 31 bit primes for 5,349-. Getting the filter code to work took a bit of hacking but there was no real problem in the end. I'll see if I still have the hacked version somewhere, if I do we could (and should, for a project this size) use 31 bit large primes.

Alex

[QUOTE=fivemack;120430]Those timings are, to use a technical term, balderdash; a better estimate is 1000 a5 sieved per CPU-minute, say rather over a million a day. So we can aim to do a5 up to at least 25 million, and it would make more sense to reserve in blocks of 10^6. I'll take 0-1000000.[/QUOTE]
I'll take 24M-25M, running on two 1.86GHz cores

Edit: the post below was in response to my complaint that a 6-digit a was low for an input this size, but I'd forgotten that the inputs given to the Kleinjung tools are scaled down.

'a5' is confusingly scaled by a factor 10^3 in pol51m0b, as I'm sure you know; presumably so that they can parse the -a and -A parameters as 32-bit integers.

RSA576 is ten more digits larger than 6^383+1, so we'd be searching half as far for this C165 as they did for that C174; that sounds reasonable to me, if not verging on overkill. For a C156 I found an unusually good polynomial lurking at a5 ~ 6 billion.

Best of luck with the hunt!

[QUOTE=fivemack;120421]Find the line in that file of the form
[code]
BEGIN POLY #skewness 1018899.74 norm 4.05e+22 alpha -5.02 Murphy_E 5.03e-13
[/code]

with the largest Murphy_E number at the end, and post here the section from that 'BEGIN POLY' line to the 'END POLY' line which follows.[/QUOTE]

If you have a cat, grep and tail available you can do

[CODE]cat *.cand | grep e-13 | sort -k 10 | tail[/CODE]

to automagically retrieve the lines containing the ten highest scores.

--
Cheers,
Jes

I just started running 1M - 2M

Maybe create a new thread with the instructions and the reservations?

Taking 2M - 3M

also taking 3M - 4M

[QUOTE=JHansen;120434]If you have a cat, grep and tail available you can do

[CODE]cat *.cand | grep e-13 | sort -k 10 | tail[/CODE]

to automagically retrieve the lines containing the ten highest scores.

--
Cheers,
Jes[/QUOTE]That is almost the same command that I used when searching for the latest polynomial, but with these changes:

[CODE]cat *.cand | grep '_E ' | sort -n -k 10 | tail[/CODE]
Then if the Murphy_E goes over a power of ten (from 9e-13 to 1e-12 say), youu don't miss the larger values.


Paul

[quote]Then if the Murphy_E goes over a power of ten (from 9e-13 to 1e-12 say), you don't miss the larger values.[/quote]

In that case you want -g not -n; with just -n, 9e-13 sorts as greater than 1e-12.

Taking 10M to 12M. (the very first thing I will do with GGNFS)

P.S.: Beginner's question: What do the -p and -n options do?

[QUOTE=Andi47;120616]
P.S.: Beginner's question: What do the -p and -n options do?[/QUOTE]
-p specifies the number of factors in the high-order coefficient of the rational polynomial. -n specifies the largest norm allowed for polynomials that are generated. Notice that pol51opt has a smaller value for -n, because the first stage generates a huge number of somewhat good polynomials but the standards are higher when the polynomials are allowed to be optimized like pol51opt does.

This is a common problem with searching in general: you want to break things up such that each stage gets rid of the vast majority of choices, but every choice that's ignored could possibly have become much better if you stuck with it and tried to optimize it (which is expensive). One reason the polynomial selection tools run so fast is that the value of -n given to them is extremely stringent, so that very nearly nothing survives the first stage. Making -n a little bit bigger can give 100x the amount of output.

For example, when searching for a polynomial for a C100 the first stage runs in 5 seconds and the second stage runs in 30 seconds when using the recommended value of -n. Given that the sieving will take 4-8 hours, it would be nice to spend maybe 10 minutes instead of .5 minutes, looking for a better polynomial.

I picked the -n value for pol51m0b so that it would produce a comfortable number of outputs: I'd run a small search with -n 2e25, which produced several megabytes of output from a range of length 1000, ran polopt, then checked that a smaller value of -n gave a more reasonable number of outputs and hadn't killed off all the good hits from the larger n.

The parameters in polopt were again picked so that it ran at about the same speed as pol51m0b, with the Murphy value picked as the score for about the tenth-best polynomial coming out of a smallish run.

Anyone got 6e-13 or higher yet?

[QUOTE=Andi47;120616]Taking 10M to 12M. (the very first thing I will do with GGNFS)[/QUOTE]

Just a little note: I will usually see reservations made here, but if you make them on the factoring-forum thread

[url]http://www.mersenneforum.org/showthread.php?t=9730[/url]

then I can summarise them all in a convenient table and delete them, to make the thread tidier when the archivists from the planet Yammel come around in the twenty-ninth century to admire it. I thought asking the gerbils for editing power on one forum was already sufficiently presumptuous.

[QUOTE=fivemack;120625]I picked the -n value for pol51m0b so that it would produce a comfortable number of outputs: I'd run a small search with -n 2e25, which produced several megabytes of output from a range of length 1000, ran polopt, then checked that a smaller value of -n gave a more reasonable number of outputs and hadn't killed off all the good hits from the larger n.

The parameters in polopt were again picked so that it ran at about the same speed as pol51m0b, with the Murphy value picked as the score for about the tenth-best polynomial coming out of a smallish run.

Anyone got 6e-13 or higher yet?[/QUOTE]

I have found a nice poly at 6.74e-13 - posted in the factoring forum thread.

P.S.: With some good polynomials reported at >6e-13, it would be sufficient to set -e 6e-13 or so in the poly51opt line?

6.74e-13 is very impressive.

Yes, it would be fine to set -e 6e-13, but all it'll do is make the .cand file shorter rather than speeding up the run. I quite like setting the threshold so that the .cand file grows by a few lines an hour, so I know where everything's got up to at any moment.

I would be interested to see what the shape of the distribution of E-values both in absolute terms and as a function of x5 looks like, for which the smaller filter value is useful - if people have kept their .cand files, could I ask them to mail them (compressed) to [email]tom@womack.net[/email]

[QUOTE=fivemack;120854]Yes, it would be fine to set -e 6e-13, but all it'll do is make the .cand file shorter rather than speeding up the run.[/quote]

Making the .cand file shorter was exactly my intention with suggesting -e 6e-13.

[quote] I quite like setting the threshold so that the .cand file grows by a few lines an hour, so I know where everything's got up to at any moment.

I would be interested to see what the shape of the distribution of E-values both in absolute terms and as a function of x5 looks like, for which the smaller filter value is useful - if people have kept their .cand files, could I ask them to mail them (compressed) to tom (ät) womack (dot) net[/QUOTE]

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

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

[QUOTE=Andi47;120858]P.S.: You should obscure your mail address to avoid massive spam (spambots).[/QUOTE]OTOH, just get an efficient spam filter to read your mail for you. That way you get benefit from easy accessibility to your intended correspondents.

However, it does assume that the marginal cost of the bandwidth and cpu caused by the spam is minimal. It is for me, but YMMV.

Paul

[QUOTE=Andi47;120858]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.)[/QUOTE]

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

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

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.

[QUOTE=fivemack;120866]Sending them would be kind, thanks. They really shouldn't be that long: I'm not getting more than 100k uncompressed per million searched.
[/QUOTE]

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.

[QUOTE=Andi47;120867]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.[/QUOTE]100K per million seems a bit low. I have about 1.25M for a 2 million range.

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.

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.

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

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

[B]memory use: 1405.0 MB[/B]

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.

[QUOTE=fivemack;122334]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.
[/QUOTE]
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
[QUOTE]
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.
[/QUOTE]
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 [url="http://www.mersenneforum.org/showpost.php?p=112982&postcount=179"]here[/url].

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

[quote=jasonp;122367]Jay, Tom doesn't bother with 32-bit machines :)[/quote]

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

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.

[QUOTE=Jay;122386]You mean some people don't use Billy Boy's Window machines? :huh:

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.[/QUOTE]64-bit Windows has been available for years. Many years, in the case of NT for Alpha.


Paul