Karim BELABAS on Tue, 27 Oct 1998 18:20:34 +0100 (MET)

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: Large input to gp

[Roland Dreier:]
> I have the output of a gp program which produced a polynomial of degree
> 3425 (!?) over F_5.  The program took a while to run, and I'd like to be
> able to just read the polynomial into gp and continue working.  But just
> feeding the output back in results in:
> parisize = 40000000, primelimit = 500000, buffersize = 30000
> ? res=Mod(1, 5)*sss1^3425 + Mod(4, 5)*sss1^3422 +
> [lots and lots and lots deleted here]
> + Mod(1, 5)*sss1 + Mod(3, 5)
>   ***   the PARI stack overflows !!!
>   ***   Warning: doubling stack size; new stack = 80000000.
>   ***   not enough memory
> What should I do here?

The problem is that given the form used to save the polynomial, GP has to
expand the expression, doing one addition at a time, allocating a huge chunk
of memory to hold the new polynomial (and all its coefficients, there's no
sparse representation in PARI...) each time. Since the formula is not really
parsed in advance, no garbage collecting can occur at this point, hence the
stack overflows quickly.

The "easy" way to recover your polynomial is to cut it into smaller pieces
in your file. A better solution (assuming you have perl on your machine):

1) Save the following script, say, in sos.pl
(maybe change the first line to the actual location of the perl binary on
your system, e.g /usr/bin/perl under Linux)

print "[";
  s/\+/,/g; s/\n//; print;
print "]";

2) Assuming the polynomial is in file bigpol, type (under GP)

  vec = extern("sos.pl bigpol"); \\ creates a vector from the coefficients
  pol = Polrev(vec, sss1);       \\ recover the polynomial.

This should work with default stack...


P.S: Next time, try to save Vec(lift(pol)) and not pol itself...
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
PARI/GP Home Page: http://pari.home.ml.org