polredabs()

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

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/