1870L : Yield Rate

[R.D. Silverman]

I have updated my siever to handle larger large primes, and
recompiled with a larger sieve region per special q.

I am a bit concerned about the yield and wonder if I might still
have bugs.

With factor base bounds of: 14.5 million for the algebraic side (925K ideals)
and 86M for the rational (5 million ideals), large prime bounds of just under
30 bits on the algebraic side and just under 31 bits on the rational, I am getting a yield of about 4 relations per special q for q near 60 million.
This seems too low.

The sieve region is 9K x 18K for each special q. Sieving one special-q
takes 17 seconds on my laptop (2.4Ghz i5) and about 13 seconds on
a 3.2 Ghz core.

The siever requires 850Mbytes of memory.

Can anyone with experience with large(r) quartics suggest whether my
yield rates might be too low?

[Batalov]

I'll try to sieve with similar parameters.

For the similarly difficult 5,815L, the yield was lowish... so instead of sieving over a huge range we set out to sieve with lasieve16e (if I am not mistaken, that's over a 32Kx64K area; correct me here, guys, who remembers better); it was as fast (rel/s) as 15e and had 3 times the yield.

I am not sure what yields Raman is getting for his new reservations for the 2,2334L/M (nominal snfs diff.234) and for 10,590M and 2,985- (nominal snfs diff.236 and 237), but if he has his cluster available only until April it will appear to be a miracle if he finishes even one of these. He's got five.

[frmky]

Yep, that's low. Using

n: <the number>
skew: 1.41
c4: 1
c3: -2
c2: -6
c1: 12
c0: -4
Y1: 2^93
Y0: -(2^187+1)
alim: 14500000
rlim: 86000000
lpba: 30
lpbr: 31
mfba: 60
mfbr: 62
alambda: 2.6
rlambda: 2.6

which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.

[Raman]

Originally Posted by Batalov

I am not sure what yields Raman is getting for his new reservations for the 2,2334L/M (nominal snfs diff.234) and for 10,590M and 2,985- (nominal snfs diff.236 and 237), but if he has his cluster available only until April it will appear to be a miracle if he finishes even one of these. He's got five.

For 5,415+ I sieved upto 190 million range of special-q upon that rational side, from (110M-300M) with help of gnfs-lasieve4I15e. I presume that was anyway oversieved, 170M range would have been enough in order to build a matrix.

I got matrix of 14332614 rows, it will take upto 11 more days in order to finish off, at this moment. It is 68% done.

For rest of numbers, I only expect around 220 million range of special-q each, upon every number (on the rational side) over that average scale.

For 5,415+ I made use of following parameters:

n: 409070648357903876177895795121676558808515790800199330391475022633084608638318069844299258901345227277398314550159052254251424043657457443453213674736966457975676435972876537687720951817693078563918161701
m: 10339757656912845935892608650874535669572651386260986328125
c4: 1
c3: -1
c2: 1
c1: -1
c0: 1
skew: 1
type: snfs
rlim: 200000000
alim: 33554431
lpbr: 31
lpba: 29
mfbr: 62
mfba: 58
rlambda: 2.6
alambda: 2.6

[R.D. Silverman]

Originally Posted by frmky

Yep, that's low. Using

n: <the number>
skew: 1.41
c4: 1
c3: -2
c2: -6
c1: 12
c0: -4
Y1: 2^93
Y0: -(2^187+1)
alim: 14500000
rlim: 86000000
lpba: 30
lpbr: 31
mfba: 60
mfbr: 62
alambda: 2.6
rlambda: 2.6

which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.

This is what I suspected..... Can you send/post the relations that it found?
Tracking down missed relations can be a real nuisance. The problem could
be anywhere........

[R.D. Silverman]

Originally Posted by frmky

Yep, that's low. Using

n: <the number>
skew: 1.41
c4: 1
c3: -2
c2: -6
c1: 12
c0: -4
Y1: 2^93
Y0: -(2^187+1)
alim: 14500000
rlim: 86000000
lpba: 30
lpbr: 31
mfba: 60
mfbr: 62
alambda: 2.6
rlambda: 2.6

which I believe matches your parameters, and sieving using 14e (which has a slightly smaller sieve area of 16K x 8K), I sieved the range q = 60M to 60M+500. There were 27 special-q in the range, and it found 229 relations at a rate of 0.64 sec/relation on the slow Opteron (a Core 2 would get under 0.4 sec/relation). This is about 8.5 rels/special-q using a smaller sieve region.

For you inputs: what are the last 4 parameters? mfba, mfbr, alambda,
rlambda?

[R.D. Silverman]

Originally Posted by R.D. Silverman

For you inputs: what are the last 4 parameters? mfba, mfbr, alambda,
rlambda?

I suspect that I may have to give up on 2,1870L.

My siever was first written 7 years ago.... It was not designed to handle
numbers of this size; it is very memory inefficient, and uses Pollard
style sieving: one computes a reduced basis for each prime in the factor
bases, yielding a skewed sieve region for each one. The boundaries of
the region need to be computed... This is overhead that is not incurred
by the Kleinjung approach.

The bucket sieving is also a memory pig;

I fear that I may have to redesign/rewrite the siever completely.
However, the only remaining Cunningham composites within reach of
my resources (even with a more efficient siever) are 2,1870L, 2,1870M.

A complete rewrite would take many months (I have real work).

In order to finish 2,1870L, I will need to track down why my yield rate
is low. Otherwise, a simple calculation shows that I will run out of
30-bit special q's before collecting enough relations to finish.

[schickel]

Originally Posted by R.D. Silverman

For you inputs: what are the last 4 parameters? mfba, mfbr, alambda,
rlambda?

Here's a quote from Chris Monico's draft documentation for the GGNFS suite:

Originally Posted by cmonico

‘rlambda’ describes how far from perfect sieve values we should actually look for good relations. It is essentially a fudge factor, and higher means more sieve entries will be closely examined. If this is too low, you’ll miss too many potential good relations. If it’s too high, the siever will spend too much time looking at locations which do not give a good location. Generally, good values are somewhere between 1.5 and 2.6 (maybe even a little larger - I haven’t done any very large factorizations yet, so I don’t have enough experience to say for sure). You guessed it - ‘alambda’ is the same thing on the algebraic side.

[R.D. Silverman]

Originally Posted by Batalov

I'll try to sieve with similar parameters.

For the similarly difficult 5,815L, the yield was lowish... so instead of sieving over a huge range we set out to sieve with lasieve16e (if I am not mistaken, that's over a 32Kx64K area; correct me here, guys, who remembers better); it was as fast (rel/s) as 15e and had 3 times the yield.

32K x 64K is 2 Gbytes! That is just the sieve array. It does not
include storage for the factor bases, polynomial roots, etc. I thought that
the 16e siever fit in just over 1 Gbyte?

Run time should be proportional to the sieve area.... A larger sieve area
means that the coordinates of the lattice points (a,b) will be larger on
average. Thus one would expect norm(a,b) to be somewhat larger and
the yield rate (per unit area) lower for a larger region. Yet you say
that the 16e had 3 times the yield of 15e and was every bit as fast.
This puzzles me.

It is clear that I need to completely re-write my siever. Whether I can
still do 2,1870L will depend on whether I can solve the yield problems.

[Batalov]

Even KF siever gets strained on quartics above 230. Around 230 is where the 16e siever becomes a good contender (it is a bit slower, but yields not 2 but almost 3 times more, and that allows to sieve in a lesser range and with twice lower FB limits; and given that, it goes on par if not better than 15e). Also around 230, LP limits will have to be doubled (viz. 30/32).

For "normal" numbers, 16e becomes useful only around 270. So there, again, roughly quartics-230 are as hard as sextics-270.

[jasonp]

The KF siever does not explicitly declare the entire rectangular (c,d) plane when sieving by vectors; instead it uses a continued-fraction-based method to determine the approximate region of the (c,d) plane where each factor base entry will hit next, then bucket sorts based on that. While I haven't examined the source closely, it probably fills up a small rectangle of the (c,d) plane at a time.