mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-11-14, 14:06   #1
chris2be8
 
chris2be8's Avatar
 
Sep 2009

7E916 Posts
Default Oversieving

Roughly how much oversieving is needed to: 1) Minimize total time if all the work is done on one system? 2) Minimize time taken in postprocesing? 3) Minimize peak memory use postprocessing? Thanks in advance. Chris K
chris2be8 is offline   Reply With Quote
Old 2009-11-14, 14:13   #2
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
Roughly how much oversieving is needed to: 1) Minimize total time if all the work is done on one system? 2) Minimize time taken in postprocesing? 3) Minimize peak memory use postprocessing? Thanks in advance. Chris K
Any oversieving (but not too much) will should do 2) and 3).

Last fiddled with by 10metreh on 2009-11-14 at 14:14
10metreh is offline   Reply With Quote
Old 2009-11-14, 20:22   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

24·13·17 Posts
Default

The answer depends on the problem size, which determines how much time the linear algebra takes out of the total. For problems that fit comfortably onto one machine, you should stop sieving as soon as a matrix can be constructed. Larger problems can benefit from adding maybe 5-10% more relations past this point. By the time you get to really huge problems, 50% oversieving may be called for; you get diminishing returns from adding more relations, and if the first matrix will be very difficult then you have to reduce its size by a great deal.
jasonp is offline   Reply With Quote
Old 2010-03-12, 17:43   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

246228 Posts
Default Too much oversieving

I know this has been discussed somewhere on the forum but I can't find the discussion despite having skim-read hundreds of posts in the msieve sub-forum.

A small (c175) SNFS factorization is predicted to take 12.6M relations, in line with previous factorizations of similarly sized numbers. It has already reached that and has gone well beyond it; it is currently well over 16M relations. Even so, the msievefact.py script claims that more relations are needed. Running msieve stand-alone with -nc or -nc1 hasn't yet done anything useful.

Would someone please point me at the posting where this issue is resolved?

Paul
xilman is offline   Reply With Quote
Old 2010-03-12, 17:47   #5
axn
 
axn's Avatar
 
Jun 2003

132·29 Posts
Default

Quote:
Originally Posted by xilman View Post
A small (c175) SNFS factorization is predicted...
Maybe it's just your prediction that is off? (somewhere between 0.7-0.8 times (pi(lpba) + pi(lpbr))

What are your large prime bounds?
axn is online now   Reply With Quote
Old 2010-03-12, 19:55   #6
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

Quote:
Originally Posted by axn View Post
Maybe it's just your prediction that is off? (somewhere between 0.7-0.8 times (pi(lpba) + pi(lpbr))

What are your large prime bounds?
I have seen snfs-176 which was happy with 9.5M relations (8.8M unique). I don't know which large prime bounds Bsquared used for this one.

Edit @ Xilman: With lpbr/a one bigger than Bsquared used, you might need ~18M relations.

Last fiddled with by Andi47 on 2010-03-12 at 19:58
Andi47 is offline   Reply With Quote
Old 2010-03-13, 19:29   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·17·313 Posts
Default

Quote:
Originally Posted by Andi47 View Post
I have seen snfs-176 which was happy with 9.5M relations (8.8M unique). I don't know which large prime bounds Bsquared used for this one.

Edit @ Xilman: With lpbr/a one bigger than Bsquared used, you might need ~18M relations.
With each of those set to 27 bits, I expect around 12M relations to be needed. In practice, 12.06M+ relations were sufficent.

I gave up in the end and re-ran the factorization from scratch on a 64-bit RHEL box. The failing system ran 64-bit Win7. Everything went fine and the program is now in the sqrt phase, which I confidently expect to fail. When it happens, I'll transfer everything to a Windoze system to get the factors.

Luckily, I have both Linux and Windoze machines, both Perl and Python drivers available. Ho hum.

Paul

P.S. Yup, it failed ...
xilman is offline   Reply With Quote
Old 2010-03-13, 21:51   #8
chris2be8
 
chris2be8's Avatar
 
Sep 2009

34×52 Posts
Default

Quote:
Originally Posted by xilman View Post
A small (c175) SNFS factorization is predicted to take 12.6M relations, in line with previous factorizations of similarly sized numbers. It has already reached that and has gone well beyond it; it is currently well over 16M relations. Even so, the msievefact.py script claims that more relations are needed. Running msieve stand-alone with -nc or -nc1 hasn't yet done anything useful.
Paul
Please post the full parms you are using. Either the name.poly or (one of) the job file(s) would give us something to look at.

Chris K
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"lanczos error: only trivial dependencies found" with massive oversieving eigma Msieve 21 2015-05-28 03:27
Oversieving + estimate of relations needed RedGolpe Msieve 10 2009-06-15 15:32
v1.40 patch for massive NFS oversieving jasonp Msieve 18 2009-04-09 03:20
Extreme oversieving and msieve jbristow Msieve 8 2008-01-02 21:43
Oversieving in msieve fivemack Msieve 1 2007-09-28 18:26

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

Tue Apr 13 06:49:39 UTC 2021 up 5 days, 1:30, 1 user, load averages: 1.38, 1.49, 1.58

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.