Re: q-polynomials (linearized polynomials, or p-polynomials) in PARI/GP?

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

On Thu, May 07, 2009 at 01:47:17PM +0300, Aurimas Fišeras wrote:
> Hello,
> I'm writing some algorithms that deal with q-polynomials ([Ore33],
> [LN84]). If I store them in PARI as regular polynomials they take a lot
> of space (e.g. q-degree=10 2-polynomial is stored internally as degree
> 1024 pol[mod]).
> 
> However, if I store them as vectors, (where vector's component number
> represent q-degree, and vector holds only coefficients (variable x is
> presumed), i=pos-1, x^(q^i) + x^(q^i) + ...) all operations with them
> are quite difficult to perform.
> 
> For example:
> simple substitution with regular polynomial:
> Px=x^4+2*x^2+3*x;
> a=2;
> subst(Px, x, a);
> %1 = 30
> 
> same 2-polynomial efficiently coded as vector:
> qPx=[3,2,1];
> res=0;for(i=1,length(qPx),res+= qPx[i] * a^(2^(i-1)));
> res
> %2 = 30
> 
> 1. Is there a more elegant way to work with q-polinomials in PARI?

I would suggest the function
qexpand(x,q,n)=
{
  local(V=vectorv(n));
  V[1]=x;
  for(i=2,n,V[i]=V[i-1]^q);
  V
}
Then you can do
qeval(P,x,q)=P*qexpand(x,q,#P)


> 2. Is there any other computer algebra system that can work natively
> with q-polynomials (I couldn't find any)?

You might try a computer algebra system that handle sparse multivariate
polynomials and treat your q-polynomials as sparse polynomials.

Cheers,
Bill.