Karim BELABAS on Fri, 25 Oct 2002 12:34:58 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
polredabs() |
Hi pari-dev, prompted by a recent query of Igor, I looked out into the following (documented) polredabs problem: ------------------------------------------------------------------------------ Warning: this routine uses an exponential-time algorithm to enumerate all potential generators, and may be exceedingly slow when the number field has many subfields, hence a lot of elements of small T_2-norm. E.g. do not try it on the compositum of many quadratic fields, use polred instead. ------------------------------------------------------------------------------ Igor's original example was { p10 = x^10-x^9+x^8-x^7+x^6-x^5+x^4-x^3+x^2-x+1; forprime(k=2, 9!, d = -5*k; if (!isfundamental(d), next); p20 = polcompositum(quadpoly(d), p10)[1]; print1(k" "); gettime; t = polredabs(p20, 16); print(gettime); ) } We polredabs() the generator of a degree 20 field, say K, where a subfield/subspace of dimension 10 (= Q(zeta_11) ) is spanned by tiny elements (roots of unity). Essentially, the search examines vectors in [-300,300]^10 x [0,1]^10 (coordinates wrt a T2-LLL-reduced basis (b_i) of some order of K, in general the maximal order). Where elements of the form [-300,300]^10 x {0} always generate a subfield ---> huge futile search. I had originally (~4 years ago) addressed this problem by computing the compositum of the field generated by the first (b_i), finding out the largest index k such that Q(b_1,...,b_k) is a strict subfield of K. Then I prune out all the [x_1,...,x_k, 0, ..., 0] from the search tree. The algorithm is still exponential (in the dimension), but I had hoped to remove cheaply common worst case situations. Unfortunately, computing a compositum is (was, see below) costly (~ computing a resultant over Z[Y], then factoring in Z[X] the resulting polynomial whose degree is the product of the compositum degree). So I had placed a heuristic limit for this strategy: if at some point the polynomial we will have to factor has degree >= 64, abort the optimization and immediately start the search [ Note: factorization worst case in this degree range is the compositum of 5 quadratic fields, yielding 16 modular factors ~ 2^15 recombinations ]. In Igor's case, of polynomial of degree 10 x 10 = 100 appears [ compositum of polcyclo(11) with a perturbated copy ], skipping part of the optimization (we find k = 6, says instead of 10), making the search feasible, but very slow. Now that van Hoeij's factorizer has stabilized and trivializes (integral) polynomial factorization, I have increased the limit to 128. I will eventually either remove it altogether [ changing Igor's p10 to p12 = polcyclo(13), we hit the limit again, 144 > 128 ... ], or use more refined heuristics. For instance, in these compositum computations, we factor at worse a polynomial of degree ( [K:Q]/2 )^2, but the degree is a poor indicator. It would be worthwile to directly evaluate the number of modular factors by computing the two-variable resultant and the factorization over Z/p for a few (relatively large) small primes. Does anybody see timing regressions for polredabs() at this point ? Anybody wants to compile a list of interesting "tough" polynomials for polredabs() ? Karim. -- 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/