Re: Memory use when factoring big polynomials

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

[Roland Dreier:]
> I recently asked gp to factor a polynomial of degree 3425 over F_5, and
> even with 40M of memory, gp still ran out of stack space.  The culprit
> appears to be very profligate use of memory with polynomial GCDs; even
> taking the GCD of two polynomials of this degree can use up all of gp's
> memory.
> 
> I wouldn't exactly describe this as a bug but I would say that gp needs
> improvement here.  For comparison, Shoup's NTL can factor my polynomial in
> a few minutes using maybe 4M of memory, so gp could do a lot better.
> 
> I got lost looking at ggcd in polarit2.c (admittedly, I didn't spend much
> time poking around).  Perhaps someone who understands the code better can
> explain where the problem is.

I've rewritten this part for version 2.0.12 (due to the initial message of
Igor Schein on this list, complaining about factor(x^120-1) taking ages).

The real culprit is "generic computation" here, which causes millions of
unnecessary copies and divisions whenever you're working in a finite field.
2.0.11 (and all previous versions) was completely unable to deal with
polynomials of degree bigger than, say, 1000 in a satisfactory way. You'd
immediately get a SEGV when trying to factor such a beast over Z for instance
(fixed-size buffers, targeted for degree less than 700...).

I'll let Igor comment on benches about the situation in version 2.0.12 if he
feels like it (he has done a tremendous amount of testing). The 2.0.12 update
is long overdue (sorry about that, too much work, too many things included).
I'll try to release it next week.

I had initially decided to make a stable release first (2.1, say), but I've
changed so many things in the meantime (to really fix problems and not simply
patch the obvious bug) that I don't think it's a good idea anymore. I'm even
hesitating to still call it "beta" ...

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