Karim BELABAS on Fri, 30 Oct 1998 13:07:37 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Memory use when factoring big polynomials |
[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