Re: wishlist: evaluating polcyclo() and others

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

* Jeroen Demeyer [2007-11-08 23:16]:
> This is a long-time wishlist item of mine.  It concerns the functions which 
> compute certain polynomials, for example polcyclo(), polchebyshev(), 
> pollegendre() and maybe others.  These functions take an argument which is 
> the variable, but I would really like to put anything there, for example 
> polcyclo(10^6, 2) would compute the value of the 10^6-th cyclotomic 
> polynomial at the point 2.  Or polchebyshev(10^4, x*Mod(1,3)) to get the 
> 10^4-th Chebyshev polynomial mod 3.  Essentially polcyclo(n,a) should be 
> the same as subst(polcyclo(n),x,a).

Done in CVS for polcyclo [ proof of concept first... ]. I started by improving
the algorithms so that polcyclo(10^6) no longer requires about 5 minutes
(---> 12ms, reducing to squarefree n helps a lot on this example...)

Indeed, inline evaluation is usually faster:

(15:16) gp > subst(polcyclo(2*3*5*7*11*13*19), x, 2);
time = 1mn, 1,876 ms.
(15:17) gp > polcyclo(2*3*5*7*11*13*19, 2);
time = 1,568 ms.

But I am using different formulas for the formal and "evaluated" computation, 
so that subst(polcyclo(n),x,a) MAY be faster than polcyclo(n, a) if a lives in
a ring allowing coefficient explosion. The reason is that the 'subst' variant
does not use divisions in the base ring (only over Z[X], with small operands),
whereas the direct 'polcyclo(n,a)' does, possibly with huge operands.

Native kernel: (first version)
(15:18) gp > polcyclo(10^6,2);
time = 2,416 ms.
(15:18) gp > subst(polcyclo(10^6),x,2);
time = 20 ms.

GMP kernel:
(15:18) gp > polcyclo(10^6,2);
time = 212 ms.
(15:18) gp > subst(polcyclo(10^6),x,2);
time = 36 ms.

I added a heuristic check in the code: if 'a' looks "huge", compute
polcyclo(n, a) essentially as subst(polcyclo(n), x, a). And the above problem
mostly disappears:

Native kernel: (after patch)
(15:18) gp > polcyclo(10^6,2);
time = 4 ms.

Still, inputs like polcyclo(n, Mod(1,2)*x) are a terrible idea compared
to the old polcyclo(n) * Mod(1,2)  [ 1) cyclotomics have tiny coeffs, so
INTMODs don't help, 2) INTMODs are slow ]

Cheers,

    K.B.
--
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`