mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-06-06, 17:09   #1
shaileshsp29
 
Jun 2006

5 Posts
Default can any one help me

hi friends,
filtering the sieve matrix is on of the important steps. can any one please inform me acutal algorithm used in GGNFS or any recent literature available regarding the same. I know only one by pomerance-smith and S. cavallar.
shaileshsp29 is offline   Reply With Quote
Old 2006-06-06, 17:29   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
Originally Posted by shaileshsp29
hi friends,
filtering the sieve matrix is on of the important steps. can any one please inform me acutal algorithm used in GGNFS or any recent literature available regarding the same. I know only one by pomerance-smith and S. cavallar.
The CWI GNFS suite includes the clique algorithm implemented by
S. Cavallar.

I have also implemented filtering code (15 years ago!) based upon the
intelligent Gaussian elimination ideas of A. Odlyzko. It was written in
Fortran (!!), and is *not* competitive with the CWI code in terms of the
quality of the final matrix. I use the CWI code. While it has a few quirks
and bugs, it produces excellent results. (but it needs quite a bit of
manual coaxing to work well)

If you do a web search on Stephania's name, I am sure her paper will turn up:

Strategies in Filtering in the Number Field Sieve
CWI Report MAS-R0012
R.D. Silverman is offline   Reply With Quote
Old 2006-06-06, 17:36   #3
asl
 
Jul 2005
Saint Petersburg, Russia

58 Posts
Default

Quote:
Originally Posted by shaileshsp29
can any one please inform me acutal algorithm used in GGNFS
GGNFS uses simple greedy algortihm. It produces fine matrices for small size factorizations, but is not suitable for large-scale ones.
asl is offline   Reply With Quote
Old 2006-06-07, 09:24   #4
shaileshsp29
 
Jun 2006

5 Posts
Default

To R.D. SIlverman

Thanks for your quick response. As mentioned in my pos,t i am aware of S. Cavallar's Approch and also Pomerance and Smiths' approach which is a modification over the Odlyzko's structured gaussian elimination. But S. Cavalla's thesis is atleast 5 yrs old and Pomerance and smith- odlyzko's are 15 yr old. I was wondering if some paper has been published after 2000.
shaileshsp29 is offline   Reply With Quote
Old 2006-06-07, 09:41   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by shaileshsp29
To R.D. SIlverman

Thanks for your quick response. As mentioned in my pos,t i am aware of S. Cavallar's Approch and also Pomerance and Smiths' approach which is a modification over the Odlyzko's structured gaussian elimination. But S. Cavalla's thesis is atleast 5 yrs old and Pomerance and smith- odlyzko's are 15 yr old. I was wondering if some paper has been published after 2000.
AFAIK, No.
R.D. Silverman is offline   Reply With Quote
Old 2006-06-07, 10:10   #6
shaileshsp29
 
Jun 2006

1012 Posts
Default

I believe that, the filtering was done on single high end machine (Plz correct me if this is wrong). But in future the (sieve output)matrix size is expected to go beyond 20Gb. In that case, a single high end machine wont suffice. And we can not use to many machines as well. The problem here is that the communication will turn out to be bottle-neck atleast in Pomerance-smith and S. Cavallar approach on multiple machines!
shaileshsp29 is offline   Reply With Quote
Old 2006-06-07, 10:44   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Thumbs up

Quote:
Originally Posted by shaileshsp29
I believe that, the filtering was done on single high end machine (Plz correct me if this is wrong). But in future the (sieve output)matrix size is expected to go beyond 20Gb. In that case, a single high end machine wont suffice. And we can not use to many machines as well. The problem here is that the communication will turn out to be bottle-neck atleast in Pomerance-smith and S. Cavallar approach on multiple machines!
CPU time really isn't a problem in filtering. The problem is memory. The
CWI code is not very memory efficient. (but it could be with some work;
I don't have the time)

A single 64-bit processor machine with a lot of memory (16 to 32 Gbytes)
will suffice for even the largest matrices in the near future. I do not see
multiple processors being required for filtering for quite some time.
R.D. Silverman is offline   Reply With Quote
Old 2006-06-07, 10:56   #8
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

280216 Posts
Default

Quote:
Originally Posted by R.D. Silverman
CPU time really isn't a problem in filtering. The problem is memory. The CWI code is not very memory efficient. (but it could be with some work;
I don't have the time)

A single 64-bit processor machine with a lot of memory (16 to 32 Gbytes)
will suffice for even the largest matrices in the near future. I do not see
multiple processors being required for filtering for quite some time.
Don Leclair and I worked a little bit to reduce the memory requirements of the CWI filtering process. Our concern was its egregious demands for duplicate and singleton removal, especially singleton removal.

Don wrote a duplicate remover; I wrote a quick and dirty singleton remover. My code certainly needs more work because at present it looks only at primes and not prime ideals. Nonetheless, it does a useful job.

Richard Wackerbarth and I have brainstormed a few ideas about parallel filtering, but we've not tried implementing any of them yet. Given our excessive workloads at the moment, I doubt we'll get much further in the near future.

Paul
xilman is offline   Reply With Quote
Old 2006-06-07, 13:13   #9
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

Quote:
Originally Posted by shaileshsp29
To R.D. SIlverman

Thanks for your quick response. As mentioned in my pos,t i am aware of S. Cavallar's Approch and also Pomerance and Smiths' approach which is a modification over the Odlyzko's structured gaussian elimination. But S. Cavalla's thesis is atleast 5 yrs old and Pomerance and smith- odlyzko's are 15 yr old. I was wondering if some paper has been published after 2000.
There was another recent paper on sparse gauss elimination - it's been a while and I can't find it online now - that mentioned Cavallar's work in passing. Instead of ordinary NFS filtering they suggested gauss elimination with approximate Markowitz pivoting. For the record, I thought up the same method independently while building an early version of what would become msieve, and it doesn't work very well at all.

My understanding of Cavallar's algorithm is that it actually is gauss elimination, except that the clique processing part of it only figures into how the initial matrix is built. I'm experimenting with using gauss elimination (after the clique phase) and a variant of full Markowitz pivoting, which can be efficiently implemented using a discrete priority queue. Both Odlyzko's method and Cavallar's merge phase sound like approximations to that, and I'm hoping that simpler code which doesn't approximate can produce a decent matrix. It seems to work well, though obviously I haven't thrown big problems at it. The (undocumented) source code is in the current version of msieve.

jasonp

PS: Haven't read it carefully, but for block lanczos there's

http://www.math.uu.nl/people/bisselin/flesch.pdf
jasonp is offline   Reply With Quote
Old 2006-06-08, 07:04   #10
shaileshsp29
 
Jun 2006

5 Posts
Default

thanks Jasonp
shaileshsp29 is offline   Reply With Quote
Old 2006-06-08, 14:30   #11
shaileshsp29
 
Jun 2006

58 Posts
Default

One more query,
After removing all the singletons, we need to throw out excess rows if they are more than the k extra realtions we intend to keep. There are two stratagies
1. Pomerance and Smith throw out the heavist realtions
2. S. Cavallar builds cliques of the reations that are 2-way mergable. weighs them with some heuristic and throws out the cliques with suitable priority.
My question is " is the second approach always better than the first one or its just an alternate way?" . Has any one comapred these two experimentally?
shaileshsp29 is offline   Reply With Quote
Reply

Thread Tools


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

Mon Sep 21 00:22:31 UTC 2020 up 10 days, 21:33, 0 users, load averages: 1.78, 1.65, 1.51

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.