Karim BELABAS on Fri, 14 Jun 2002 03:41:23 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: nffactor() regression |
On Thu, 13 Jun 2002, Igor Schein wrote: > the command below enters an infinite loop in 2.2.4 on Alpha Linux. It worked > fine in 2.2.3 [...] I and Xavier Roblot have been refurbishing my relative variant of van Hoeij's method (to factor polynomials over number fields). We had not yet tested it on 64 bit machines yet ! It broke in a trivial place. It is fixed (typo in nf_factor_bound, due to 3 == DEFAULTPREC on 64bit). Btw, it would be a good idea to test heavily the polynomial factorization routines, over Q (factor), and number fields (nffactor) [ factornf implements Trager's method + van Hoeij over Z and is a desperate case unless the degree of the field is very large compared to the degree of the polynomial. It doesn't really require testing... ]. I have just (committed one hour ago) made important modifications to the algorithm in the past week. Altough it works much better for my examples, I might have broken something else. ( Van Hoeij's method is not exactly an obvious thing to implement, and will require a lot of tuning. ) You can see most relevant details at \g3. I had tested Paul Zimmermann's factorization challenges http://www.loria.fr/~zimmerma/mupad/ before the release, so I'm probably tuned all right with respect to these. It would be a good idea to check other types of polynomials. Cheers, Karim. P.S: The weak parts of the implementation are (quadratic) Hensel lifting for large degrees and huge heights and, in nffactor, the computation of an LLL-reduced basis for \wp^k in nffactor (when k is large, say 100 and more). For the latter it may be the weak part of my algorithm, with nothing really to blame about the implementation. I don't know yet. As for Hensel lifting, for the tough examples (say degree 1000, 4000 digits) it requires very efficient polynomial arithmetic, which we don't have. In particular, all euclidean divisions should be preconditionned; also, we're definitely in the FFT zone in that range, and we don't have one. Victor Shoup's NTL (5.0c + gmp-3.1.1) is between 3 and 4 times faster than Pari for this kind of inputs (already about twice faster for degree 500, 400 digits). There are some impressive NTL timings at http://shoup.net/ntl/doc/tour-time.html -- Karim Belabas Tel: (+33) (0)1 69 15 57 48 Dép. de Mathematiques, Bat. 425 Fax: (+33) (0)1 69 15 60 19 Université Paris-Sud Email: Karim.Belabas@math.u-psud.fr F-91405 Orsay (France) http://www.math.u-psud.fr/~belabas -- PARI/GP Home Page: http://www.parigp-home.de/