Joerg Arndt on Mon, 10 Apr 2006 12:17:05 +0200

 Re: Pol problem (bug?)

```* Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr> [Apr 10. 2006 11:50]:
> * Joerg Arndt [2006-04-09 11:27]:
> > I do not see a system here:
> >
> > ? Pol([a,b,c])
> > a*x^2 + b*x + c
> > ? Pol([a,b,c],d)
> > a*d^2 + b*d + c
> > ? Pol([a,b,c],x)
> > a*x^2 + b*x + c
> > ? Pol([a,x,c])
> > a*x^2 + x*x + c
> > ? Pol([a,x,c],'x)
> > a*x^2 + x*x + c
> >
> > ? Pol([a,x,c],'x_)
> >   *** Pol: main variable has highest priority in gtopoly.
> > ? Pol([a,x,c],'a_)
> >   *** Pol: main variable has highest priority in gtopoly.
> > ? Pol([a,x,c],'z_)
> >   *** Pol: main variable has highest priority in gtopoly.
>
> I have reworded the error message and fixed an off-by-1 problem. The
> correct behaviour (current CVS, clean session) is

Fine, thanks.

>
> ? Pol([a,b,c])
> %1 = a*x^2 + b*x + c
> ? Pol([a,b,c],d)
>   *** Pol: variable must have higher priority in gtopoly.
> ? Pol([a,b,c],x)
> %2 = a*x^2 + b*x + c
> ?  Pol([a,x,c])
>   *** Pol: variable must have higher priority in gtopoly.
> ? Pol([a,x,c],'x)
>   *** Pol: variable must have higher priority in gtopoly.
> ? Pol([a,x,c],'x_)
>   *** Pol: variable must have higher priority in gtopoly.
> ? Pol([a,x,c],'a_)
>   *** Pol: variable must have higher priority in gtopoly.
> ? Pol([a,x,c],'z_)
>   *** Pol: variable must have higher priority in gtopoly.
>
> > what is a "main variable"?
>
> (09:38) gp > ??Pol
> Pol(x,{v = x}):
>
>    transforms the object x into a polynomial with main variable v. [...]
>    Warning: this is not a substitution function.   It will not transform an
> object containing variables of higher priority than v.
>
>    ? Pol(x + y, y)
>      *** Pol: variable must have higher priority in gtopoly.
>
> See also Section 2.5.4 (p. 39, current CVS) of the User's manual, on
> "Variable priorities, multivariate objects"

I'll do that.

>
> > There does not seem to be a workaround.
>
> There might be. What are you trying to achieve ?

I compute recurrences via modular polynomial exponentiation,
see http://www.jjj.de/pari/fastrec.inc.gp

The (topmost) function vec2charpol() used by frec() (bottom
of file) fails sometimes with symbolic recursions, e.g.
when trying to compute Fibonacci polynomials.

? frec([1,x],[2*x,-1],3)
*** Pol: main variable has highest priority in gtopoly.
? frec([1,a],[2*a,-1],3)
time = 0 ms.
[4*a^3 - 3*a, 8*a^4 - 8*a^2 + 1]

? a=33;
? N=100000;

? f=frec([1,a],[2*a,-1],N)[1];
time = 46 ms.
\\ same does not work with builtin:
? t=subst(poltchebi(N,x),x,a);
*** poltchebi: the PARI stack overflows !
current stack size: 256000000 (244.141 Mbytes)
[hint] you can increase GP stack with allocatemem()

The frec() function allows to compute term of general
(linear, homogeneous) recurrences very fast.

Compare to the builtin fibonacci():
? n=1000000;
? f=frec([0,1],[1,1],n)[1];
time = 57 ms.
? t=fibonacci(n);
time = 38 ms.
? t-f
0

... but you get any order:
? f=frec([0,0,0,1],[1,1,1,1],n)[1];
time = 352 ms.

>
> 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]

All the best,
jj

P.S.:
my attempt for SVD: http://www.jjj.de/pari/matsvd.inc.gp
some hypergoemetric stuff: http://www.jjj.de/pari/hypergeom.inc.gp

```