From: Mark van Hoeij
Subject: timings of the new version
Date: Mon, 17 Jul 2000 17:39:40 -0400 (EDT)
Content-Type: text/plain; charset=us-ascii



These are the timings of the new version, on a Pentium 266 laptop
in Maple 6. The polynomials are P1,..P8 obtained from Paul Zimmerman's
web-site:     http://www.loria.fr/~zimmerma/mupad/

time1 = 3.521
time2 = 20.540
time3 = 24.120
time4 = 7420.901  (time dominated by Hensel lifting)
time5 = 107.319
time6 = 56.511
time7 = 3261.989
time8 = 8699.380  (time dominated by Hensel lifting)

Comments:

P1, P2, P3: knapsack factorization was not used because there
few modular factors, so these timings are Maple 6 combined
with the d-1 test I added to Maple's code. For these small examples
the d-1 test probably makes little difference, however.

P4: Hensel lifting takes 6580 sec. Searching for combinations
of 1, 2, or 3 modular factors with Zassenhaus takes 33 sec.
Then knapsack takes 807 seconds.

P5: about 16 seconds is lost due to the fact that Maple first
tries p(x^(1/2)), which is in general of course a good strategy.

P6: Maple applies the p(x^(1/2)) which is quite succesful because
after this trick, Maple's `factor/combfact` finds 4 factors of
degree 6 (which become degree 12 if you put x^2 back for x again),
so the knapsack method only needs to handle the remaining 16 modular
factors, which it has to do twice because after the p(x^(1/2)) one
still has to factor the factors one obtained of p(x).

P7: first it tries p(x^(1/2)), takes about 540 sec. Then Hensel
for p(x) takes 590 sec. Then searching for combos of 1, 2, or 3
modular factors takes 160 seconds. Then knapsack takes 1975 sec.

P8: Hensel takes 7915 sec. Searching for combo's of 1, 2 or 3
modular factors takes only 7 seconds (before I added the d-1
test to Maple's Zassenhaus this took thousands of seconds).
Then knapsack takes 755 sec.