5^421-1 sieving (reservations closed)

[jasonp]

You guys are really cruising. Tom, you can make msieve's duplicate removal a lot more efficient in the presence of huge numbers of relations by changing LOG2_DUP_HASHTABLE1_SIZE in gnfs/filter/duplicate.c to something like 30 or 31; that should reduce the memory use at least. You can also try incrementing LOG2_DUP_HASHTABLE2_SIZE, though this will make the hashtables significantly larger.

I should be releasing v1.37 in the next week or two, and this will have a few filtering improvements

[fivemack]

We've just reached the hundred-million-Q point in relations uploaded, in under a month since sieving started; so we've been averaging about forty cores contributing to the project.

I think we have two months to go. Thanks to everyone who's contributing cycles!

[Batalov]

I've put 176M and 177M. 178-179M, 179M-180M are in progress.

There are a bit smaller than 174M and 175M. I have now realized that I had inadvertently run the 14e siever on a few small sub-chunks. But I will use consistently 15e for my other (and future) chunks. Understandably, there's nothing wrong with the 14e results, just fewer.

P.S. I have to confess that I've slowed down because I tried my muscle on two other numbers, 7,384+ and 2-1586L/gnfs. Will catch up. Promise.

-Serge

[fivemack]

Thu Aug 28 01:42:30 2008  restarting with 174092090 relations
Thu Aug 28 02:38:00 2008  found 15396903 duplicates and 158695148 unique relations
Thu Aug 28 02:39:57 2008  filtering rational ideals above 202571776
Thu Aug 28 02:39:57 2008  filtering algebraic ideals above 202571776
Thu Aug 28 03:14:52 2008  158695148 relations and about 99916465 large ideals
Thu Aug 28 07:10:46 2008  reduce to 28551117 relations and 20303495 ideals in 25 passes

Given duplicates, we're just under half-way there.

[bsquared]

The cluster is down for a bit, so it might be longer before I can finish the range I just reserved. Although it's down so that they can add 64+ more cores, and more memory, so it's a good down time :-)

[jasonp]

I can do line sieving if nobody is working on it already. What line size do you think is approriate for such a large job?

[fivemack]

I haven't done any line sieving myself on this one, so I've no idea what size is appropriate; 50% of the relations in one file I chose at random have |x| < 10^11, but that's probably far too long a line to be of use. Just to pull numbers from the top of my head, (2*10^10) x 10^4 would be a nice region to look at (about 6% of the relations have |x|<10^10, and the skewness is around 10^6), but I would sieve b=3456 for line lengths 2^31 through 2^37 and see how the yield/time curve looks. I suppose I'd target a CPU-month for line sieving, but I don't know how you are for CPUs.

[jasonp]

Between line sizes of 2G, 4G and 8G, the 4G had the fastest time per relation found (by around 20%). With that line size a 2GHz opteron needs approximately 30 minutes per line, so 10k lines is a fairly big chunk of runtime for me. I'll put 3 CPUs on it and see how far I get in a week. Expect something under a million relations per thousand lines.

[fivemack]

Given the skewness I think it makes sense to do 2k lines rather than 10k, though that's still an unreasonable amount of runtime.

I don't know if there's a sense in which these small-X,Y relations are better than the lattice sieving ones; unless there is, I don't think it's worth more than a few CPU-weeks.

Thanks for the data!

[jasonp]

Well, if 2500 lines of 1/8 the size took 3 CPU-days for 6,383+, then the current effort should be just a scale-up of that. A 2.6GHz core2duo system averages about 20 minutes per line (actually 26 minutes for odd lines and 14 minutes for even lines)

[Wacky]

Originally Posted by fivemack

I don't know if there's a sense in which these small-X,Y relations are better than the lattice sieving ones; unless there is, I don't think it's worth more than a few CPU-weeks.

My experience is that not only is the line siever significantly slower than the lattice siever, but given a large number of lattice relations, a disproportionately large number of them duplicate relations already found.

I attribute this to the fact that there are very few relations which are truly smooth with respect to a limit below the special-q.

In particular, for many of the line-sieving relations, one of their "large primes" matches a q value that was used as a special-q in the lattice sieving.