Oversieving

[chris2be8]

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

[10metreh]

Originally Posted by chris2be8

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).

[jasonp]

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.

[xilman]

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

[axn]

Originally Posted by xilman

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?

[Andi47]

Originally Posted by axn

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.

[xilman]

Originally Posted by Andi47

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 ...

[chris2be8]

Originally Posted by xilman

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