Claus Fieker on Fri, 08 May 2009 01:23:23 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: q-polynomials (linearized polynomials, or p-polynomials) in PARI/GP? |
On Thu, May 07, 2009 at 02:13:46PM +0200, Bill Allombert wrote: > 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. > Depends on what exactly you mean by q-polynomials and their operations. They occur naturally as additive polynomials and as endomorphisms in char. p in the Drinfeld theory for function fields as well as as twisted polynimials (or skew polynomials) in coding theory. Elementary operations motivated from here are available in Magma http://magma.maths.usyd.edu.au Greetings Claus PS.: I do know this is the pari-dev list, but he asked... > Cheers, > Bill. >