mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-03-26, 13:45   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Exclamation Lattice Optimization

I enclose some interested data and an observation.

My lattice sieve does not process all special-q's.

After reduction if the lattice is too skewed or if the reduced coefficients
are too big, I do not process that special-q. Too skewed means a condition
number of 5 or higher. Too big means one of the reduced coefficients exceeded 2^19.

Here is some data on the results of this optimization.

I ran the siever for some special-q's near 200 million on 2,776+.

In a fixed amount of time (4200 seconds):

The code that rejects special-q's looked at 897 special-q's and
rejected 439, processing 457 of them. The yield was 2262 total relations
(.53 relations/second)

The code that accepts all special-q's looked at 416 special-q's and processed
all of them. The yield was 1113 total relations (.265 relations/second)

This difference is striking. Note also that the average time to process each
special q is higher when all of them get accepted. (9.2 seconds/q when
rejecting, 10.1 seconds when accepting)

I'd really like to hear comments from others who have run the Franke
or msieve code. Do they see similar behavior?????
R.D. Silverman is offline   Reply With Quote
Old 2008-03-26, 15:54   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33×131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I'd really like to hear comments from others who have run the Franke
or msieve code. Do they see similar behavior?????
Msieve doesn't use a lattice siever; I'm currently trying to work on the polynomial selection instead (though I've been saying that for over a year now).

If nobody else responds by tomorrow I can try some tests.
jasonp is offline   Reply With Quote
Old 2008-03-31, 12:21   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001001002 Posts
Default

Quote:
Originally Posted by jasonp View Post
Msieve doesn't use a lattice siever; I'm currently trying to work on the polynomial selection instead (though I've been saying that for over a year now).

If nobody else responds by tomorrow I can try some tests.
Noone has responded. I would think that anyone interested in this subject
might be interested in an optimization with such a dramatic impact.

However, everyone seems to busy just blindly running code written by
others to take an interest in the actual algorithms........

It's pathetic.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-31, 12:30   #4
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Noone has responded. I would think that anyone interested in this subject
might be interested in an optimization with such a dramatic impact.

However, everyone seems to busy just blindly running code written by
others to take an interest in the actual algorithms........

It's pathetic.
Or, perhaps, they are busy doing something else and have not had the time to respond in a meaningful manner.

Patience, Grasshopper.
Wacky is offline   Reply With Quote
Old 2008-03-31, 12:59   #5
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2·5·13 Posts
Default

Quote:
Originally Posted by Wacky View Post
Or, perhaps, they are busy doing something else and have not had the time to respond in a meaningful manner.

Patience, Grasshopper.
I'm certainly interested in the subject but I didn't reply because
- I run my own lattice siever, not Franke's or msieve
- I'm currently spending what little time I have for this hobby on trying to find a particularly annoying bug in my square root code
When I start sieving again I may well be interested in investigating optimisations like this, since I'm certain my siever has plenty of scope for improvement.

Chris
Chris Card is offline   Reply With Quote
Old 2008-03-31, 13:39   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

It's a nice optimisation, which for some reason I thought was already in the Kleinjung code (since the paper http://www.math.uni-bonn.de/people/thor/cof.ps includes the line 'Approximately 18% of the special Q have a highly skewed lattice and were discarded'); but looking at the source code for the ggnfs-distributed version of the siever indicates that the trick isn't in the version of 2004 June 13, unsurprising since the Kleinjung paper was produced for SHARCS 2006 a couple of years after that version appeared.

I have a rather newer version of the Kleinjung siever on a machine at home, which outputs the reduced ideals for everywhere that it sieves; I'm pretty sure even that doesn't throw away skewed lattices; I'll have a look at what the relation count per prime ideal looks like as a function of the condition number of the lattice.

Last fiddled with by fivemack on 2008-03-31 at 13:47
fivemack is offline   Reply With Quote
Old 2008-03-31, 14:30   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by fivemack View Post
It's a nice optimisation, which for some reason I thought was already in the Kleinjung code (since the paper http://www.math.uni-bonn.de/people/thor/cof.ps includes the line 'Approximately 18% of the special Q have a highly skewed lattice and were discarded'); but looking at the source code for the ggnfs-distributed version of the siever indicates that the trick isn't in the version of 2004 June 13, unsurprising since the Kleinjung paper was produced for SHARCS 2006 a couple of years after that version appeared.

I have a rather newer version of the Kleinjung siever on a machine at home, which outputs the reduced ideals for everywhere that it sieves; I'm pretty sure even that doesn't throw away skewed lattices; I'll have a look at what the relation count per prime ideal looks like as a function of the condition number of the lattice.
I make the following simple and elementary observation.
Consider a square (or recantagular) lattice of area A. The number of
lattice points in the interior is just A plus or minus a small error proportional
to the perimeter. (i.e. the error is O(sqrt(A))

Now skew this lattice by an affine transform whose condition number is
C. This skewed lattice now contains far fewer lattice points than the
original. Indeed, as C gets large, the number of interior lattice points
drops to zero. To process such a latttice we must incur the same overhead
as any other lattice, but since there are few potential lattice points, there
are few potential successful relations. Note also that the skewed lattice
has the same Area as the original.

For those of you who don't follow this I suggest drawing a picture of a
long and skinny parallelogram on a piece of graph paper.......

My code does the following:

Look at the largest reduced coefficient. If it is too large, discard this
q. (A very large coefficient in the reduced lattice means that the norms
will be large and hence unlikely to be smooth). I use 2^19 as the cutoff.

Estimate the condition number. If greater than 5, discard this q.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-31, 14:45   #8
Chris Card
 
Chris Card's Avatar
 
Aug 2004

2·5·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I make the following simple and elementary
Estimate the condition number. If greater than 5, discard this q.
Which matrix norm do you use to estimate the condition number?

Chris
Chris Card is offline   Reply With Quote
Old 2008-03-31, 15:07   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by Chris Card View Post
Which matrix norm do you use to estimate the condition number?

Chris
I use the maximum of the two norms of the column vectors
divided by the sqrt of the determinant.

One could also simply compute the acute angle via a dot product
and an ACOS and reject if the angle is too acute.
R.D. Silverman is offline   Reply With Quote
Old 2008-03-31, 15:37   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101011011102 Posts
Default

I am swimming in water that is too deep for me, but I'll comment:

If q are discarded, then one would need to sieve to higher q in order to collect a fixed number of relations because yield decreases as q increases, correct? This seems like it would reduce the benefit of discarding q's (you are cherry-picking q's, but the q's you are cherry-picking from are not as good overall). Do you have a feel for if the necessarily increased q range will have significant impact: still a net benefit but not quite as much? completely irrelavent? something else?
bsquared is offline   Reply With Quote
Old 2008-03-31, 15:57   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by bsquared View Post
I am swimming in water that is too deep for me, but I'll comment:

If q are discarded, then one would need to sieve to higher q in order to collect a fixed number of relations because yield decreases as q increases, correct? This seems like it would reduce the benefit of discarding q's (you are cherry-picking q's, but the q's you are cherry-picking from are not as good overall). Do you have a feel for if the necessarily increased q range will have significant impact: still a net benefit but not quite as much? completely irrelavent? something else?
Yes, it does reduce the benefit somewhat. But my data shows that
larger 'good' q's are still better than smaller 'bad' ones. How much better
is sensitive to factor base size, large prime bounds, and sieve area per q.

Quantifying it theoretically seems out of the question, because the difference
only shows up in the o(1) term in the exponent.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
QS Lattice Siever R.D. Silverman Factoring 31 2018-10-08 17:17
Possible optimization for GIMPS alpertron Math 3 2012-08-13 16:08
Size optimization Sleepy Msieve 14 2011-10-20 10:27
NFS Optimization R.D. Silverman Factoring 91 2010-01-24 20:48
ASM Optimization Cyclamen Persicum Hardware 4 2004-05-26 07:51

All times are UTC. The time now is 00:18.

Wed May 12 00:18:33 UTC 2021 up 33 days, 18:59, 0 users, load averages: 4.00, 4.04, 3.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.