Bill Allombert on Thu, 07 May 2009 14:21:10 +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 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.