mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2004-05-25, 13:51   #1
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

1648 Posts
Default Line sieving vs. lattice sieving

Hi!

I (think) I have understood how the line siever works, but I have no clue of how the lattice siever works. Could someone please explain to me (and the rest of the group ) how the lattice siever works?

I have tried the CWI line siever and Jens Franke's lattice siever. His siever seems to be faster. Is this due to the implementation or is there a theoretical reason for the lattice siever to be faster?


---
Best regards
Jes Hansen

Last fiddled with by JHansen on 2004-05-25 at 13:52
JHansen is offline  
Old 2004-05-25, 16:36   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

237228 Posts
Default

Quote:
Originally Posted by JHansen
Hi!

I (think) I have understood how the line siever works, but I have no clue of how the lattice siever works. Could someone please explain to me (and the rest of the group ) how the lattice siever works?

I have tried the CWI line siever and Jens Franke's lattice siever. His siever seems to be faster. Is this due to the implementation or is there a theoretical reason for the lattice siever to be faster?


---
Best regards
Jes Hansen
I'll try, but please keep in mind that my explanation is (deliberately) handwaving and glosses over important detail.

If you know how the line siever works, you know then how the norms of each polynomial which are divisible by a specific prime are equally separated along the sieving line. (Handwaving warning: I mean prime ideal or, if you're happier with this phrasing, there is one such series per root of the polynomial mod p).

Right, now fix a large prime, one bigger than any in the factorbase for a particular polynomial. Call it q. Better, call it special_q because we've chosen it to be special. Now, you will again agree that norms divisible by this special-q are regularly separated in the sieving region, right? That is, they form a lattice.

The clever bit of the lattice sieve is to transform the polynomials or, entirely equivalent, the coordinate system of the sieving rectangle so that these lattice points become adjacent in the transformed system. Now sieve the transformed region with the factorbase primes. You know, a priori, that all the norms are divisible by a large prime and so, after that prime is divided out, the norm will be smaller by a factor of special-q and so (handwaving again) more likely to be smooth. Smooth is good, so you are more likely to get a relation.

That's the handwaving reason why the lattice sieve is likely to be faster than the line sieve. It completely glosses over some features which damage its performance. For a start, reducing the norm of one polynomial is likely, in practice, to increase the norm of the other. To some extent this can be counteracted by using special-q on the polynomial which typically has the greater norm. Another source of inefficiency is the requirement for the coordinate transformations for each special-q.

It's my belief that Jens Franke's lattice siever gains most of its speed over the CWI line siever from implementational differences. It has assembly language support for various x86 systems whereas the CWI siever uses much more general purpose code. The lattice siever's use of a very fast mpqs for factoring 2-large prime candidates probably outperforms the CWI-siever's use of rho and squfof, though I haven't evaluated that area in any detail.

Some of the speed increase, though, probably does come from it using the lattice sieve. Again, I haven't tried to disentangle the effects and to quantify them.

Down sides of the lattice sieve become apparent when you consider the post-sieving phases. First off, a prime can be a special-q and also a regular large prime for a different special-q and vice versa. That is, duplicate relations are almost inevitable when using a lattice sieve. The dups have to be identified and rejected. This takes computation and storage and, in a distributed computation, comms bandwidth. It also means that the raw relations/second measure isn't quite such a good measure of efficiency as it is for the line siever. Worse, the number of duplicates increases as the number of relations grows (another view of the birthday paradox) and so the effective rate of relation production falls as the computation proceeds.

Something that tends to hit the linear algebra phase is that the special-q primes act in many ways as if they were factor base primes. That is, they tend to make the matrix larger and denser compared with the relations found by a line sieve with the same factorbases. However, the argument can be turned on its head: by using a large effective factor base one can use a smaller real factorbase and so speed up the sieving without losing relations. Think about it, and you'll see that this is another way of phrasing the paragraph above beginning "The clever bit ..."

Hope this helps.

Paul
xilman is offline  
Old 2004-05-26, 15:30   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Thumbs up

Quote:
Originally Posted by xilman

<snip> Allow me to add a bit....

Right, now fix a large prime, one bigger than any in the factorbase for a particular polynomial. Call it q. Better, call it special_q because we've chosen it to be special. Now, you will again agree that norms divisible by this special-q are regularly separated in the sieving region, right? That is, they form a lattice.
They actually form a sub-lattice of the original lattice. One keeps track
of the sub-lattice by finding a basis (which is easy) then using LLL or some
other method to QUICKLY find a reduced basis. The quality of the reduction
is important. See below.

Quote:
Originally Posted by xilman
The clever bit of the lattice sieve is to transform the polynomials or, entirely equivalent, the coordinate system of the sieving rectangle so that these lattice points become adjacent in the transformed system. Now sieve the transformed region with the factorbase primes. You know, a priori, that all the norms are divisible by a large prime and so, after that prime is divided out, the norm will be smaller
Yes. But there is a "seesaw" effect. As one pushes the norms of one polynomial smaller, the norms of the other one get bigger. If the reduced
lattice isn't small enough, the decreased norm is outweighed by a bigger
increase (bigger than the decrease) in the other norm.


Quote:
Originally Posted by xilman
That's the handwaving reason why the lattice sieve is likely to be faster than the line sieve. It completely glosses over some features which damage its performance. For a start, reducing the norm of one polynomial is likely, in practice, to increase the norm of the other. To some extent this can be counteracted by using special-q on the polynomial which typically has the greater norm. Another source of inefficiency is the requirement for the coordinate transformations for each special-q.
Yes. And computing the transform does take time.

Quote:
Originally Posted by xilman
It's my belief that Jens Franke's lattice siever gains most of its speed over the CWI line siever from implementational differences. It has assembly language support for various x86 systems whereas the CWI siever uses much more general purpose code. The lattice siever's use of a very fast mpqs for factoring 2-large prime candidates probably outperforms the CWI-siever's use of rho and squfof, though I haven't evaluated that area in any detail.
I considered using QS a long time ago, but thought that SQUFOF (in single
precision) would be faster. In any event my code takes ~ 7% of the total
run time in squfof. Doubling the speed would only yield ~3% improvement in total run time. Pollard Rho is quite a bit slower than squfof, but my code
succeeds with squfof better than 95% of the time. Only if squfof fails do I use Rho.

QS looks better for the 3 large prime variation.

Here is siever data (mine) for 2,653+. The sieve length is [-13M, 13M] per
b-value. Total values sieved is 13.6 x 10^9 (26 x 2^20 x 500)

Siever built on Mar 18 2004 12:47:42
Finished processing the range 704500 to 704999 <-- b's
In 2296.507117 elapsed seconds
This is approximately 1920 Million Arithmetic Operations/sec <-- by estimated count of arithmetic ops only

<-- times are msec -->
Total sieve time = 1419237.100308 (odd b sieving plus all subroutines)
Total even sieve time = 858458.400465 ("" even b's plus subroutines)
Total resieve time = 74504.261681 (time to factor by resieving odd b)
Total even resieve time = 62589.224396 ("" even b)
Total trial int time = 12307.307793 (time for trial division; linear poly)
Total trial alg time = 208669.855863 ("" sextic poly)
Total alg scan time = 29042.052749 (time to scan for successes)
Total alg squfof time = 161006.544098 (time running squfof on sextic)
Total int squfof time = 9264.036061 ("" linear)

This last line is the actual time spent JUST sieving odd b's. Even b's
take about 55% of the odd ones.
Total asieve, isieve = 561935.884146 599546.527601

Quote:
Originally Posted by xilman
Down sides of the lattice sieve become apparent when you consider the post-sieving phases. First off, a prime can be a special-q and also a regular large prime for a different special-q and vice versa. That is, duplicate relations are almost inevitable when using a lattice sieve. The dups have to be identified and rejected. This takes computation and storage and, in a distributed computation, comms bandwidth. It also means that the raw relations/second measure isn't quite such a good measure of efficiency as it is for the line siever. Worse, the number of duplicates increases as the number of relations grows (another view of the birthday paradox) and so the effective rate of relation production falls as the computation proceeds.
Yes. comparing speed by looking at output for a short time falsely compares
the two methods because toward the end the lattice siever generates
quite a lot of duplicates.

One advantage the lattice siever has is the following. The yield rate for the
line siever decreases over time because the norms get bigger as the sieve
region moves away from the origin. The lattice siever brings the sieve region
"back to the origin" when special-q's are changed. This might be its biggest
advantage (if there is one)

Quote:
Originally Posted by xilman
Something that tends to hit the linear algebra phase is that the special-q primes act in many ways as if they were factor base primes. That is, they tend to make the matrix larger and denser compared with the relations found by a line sieve with the same factorbases. However, the argument can be turned on its head: by using a large effective factor base one can use a smaller real factorbase and so speed up the sieving without losing relations. Think about it, and you'll see that this is another way of phrasing the paragraph above beginning "The clever bit ..."
Yep. Note that in the Pollard version, the special-q's ARE factor base primes.
I have considered a version where the special-q's lie outside the factor base,
but back-of-envelope shows that the "seesaw" effect means that for such
primes, the increase in one polynomial more than offsets the decrease in
the other. Of course a better implementation might alleviate this. My lattice
siever was quite crude. I never spent much time on it.

Last fiddled with by Wacky on 2004-05-27 at 11:45 Reason: Fix quotes
R.D. Silverman is offline  
Old 2004-05-27, 11:21   #4
Death
 
Death's Avatar
 
Mar 2004
Ukraine, Kiev

2×23 Posts
Post

use [ quote="xilman" ] to make quotes (without spaces)
and [ /quote ] to close quotation (also w/o spaces)

Last fiddled with by Death on 2004-05-27 at 11:23
Death is offline  
Old 2004-05-28, 14:03   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Thumbs up

Quote:
Originally Posted by Death
use [ quote="xilman" ] to make quotes (without spaces)
and [ /quote ] to close quotation (also w/o spaces)
Ah. Thanks. I was wondering about my syntax errors....

Now. Would anyone like to discuss the lattice sieve? Or is it too
specialized a topic?
R.D. Silverman is offline  
Old 2004-05-28, 15:11   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·1,699 Posts
Default

Quote:
Originally Posted by Bob Silverman
Ah. Thanks. I was wondering about my syntax errors....

Now. Would anyone like to discuss the lattice sieve? Or is it too
specialized a topic?
My guess is the latter.

Paul
xilman is offline  
Old 2010-06-09, 15:23   #7
chris2be8
 
chris2be8's Avatar
 
Sep 2009

36308 Posts
Default

As a follow on from this I've read about classical sieving and line sieving, are they two names for the same thing? If not what is the difference?

Thanks in advance.

Chris K
chris2be8 is offline  
Old 2010-06-09, 17:19   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
As a follow on from this I've read about classical sieving and line sieving, are they two names for the same thing? If not what is the difference?

Chris K
One of its legs is both the same.
R.D. Silverman is offline  
Old 2010-06-09, 17:36   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Boy you guys reach waaaay back. I have sometimes seen sieving near the roots of the algebraic polynomial in the (a,b) plane referred to as 'line sieving'. This was terminology that Chris Monico favored but I've never seen anyone else use it.
jasonp is offline  
Old 2010-06-09, 19:25   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,699 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
One of its legs is both the same.
I thought that applied to ducks.
xilman is offline  
 

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I'm getting an error when yafu wants to start lattice sieving Hailstone YAFU 30 2018-05-23 19:33
Lattice Sieving Parameters paul0 Factoring 6 2015-11-20 21:12
Lattice Sieving - where do I start? paul0 Factoring 3 2015-03-09 13:54
A question on lattice sieving joral Factoring 5 2008-04-03 08:01
Initialization for lattice sieving jasonp Factoring 16 2006-01-12 22:53

All times are UTC. The time now is 06:04.

Fri Nov 27 06:04:29 UTC 2020 up 78 days, 3:15, 4 users, load averages: 1.57, 1.24, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.