Re: MPQS Checkpointing?

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Message-ID: <Pine.SOL.3.95.1000509154726.15746D-100000@factor.tools.gtei.net>
> From: Andrew Brown <abrown@genuity.net>
> Date: Tue, 9 May 2000 15:57:09 -0400 (EDT)
> 
> In the near future, I will be doing some semi-large (80 to 100 digit) 
> factorizations using PARI's excellent implementation of the MPQS.  I am
> wondering if there is any way to checkpoint the process to disk, as these
> factorizations can run for several weeks.

Rather less than that for 80 digits on contemporary hardware.

Some of my current benchmark examples take between 6 and 26 hours for
input of 80-84 digits, on UltraSPARC-IIi 333MHz CPUs.

100-digit input on the other hand will be quite interesting;  so far
I haven't heard of any successful attempt in this range.  (I tried it
back in 1998, but was thwarted by system crashes or routine shutdowns
each time!)

Thanks to a lot of prodding, pushing, and lateral thinking by Bill Daly,
several improvements in the MPQS code have recently been identified --
please do drop me a line off the list if you're interested in running
your examples on the current bleeding edge code.  You may find many of
them faster by anything between 10% and 35%, and I'll be happy to exploit
every opportunity to have the code crash-tested and fine-tuned on further
examples before it becomes part of the distribution one day.

> Also, using the PARI library, is it possible to split up what ranges or
> polynomials are used during the sieving process?  Can the elimination
> phase take advantage of multiple CPUs?  It would he helpful if there were
> ways to distribute the workload. 

Alas, these are still on the TODO list, and rather nontrivial to
implement, although the basic idea has been on my mind for a long
time.  (One would have to wrap some kind of client-server architecture
around the basic code, beside modularizing the algorithm.  It is not
quite clear to me that this is even feasible without impeding PARI's
portability;  a more realistic approach might be specialized factoring
`daemons' using the PARI library.)  But there's nothing to stop you
from running one gp job on each of your CPUs, each working on its own
factoring task.

Enjoy, Gerhard