Aurimas Fišeras on Thu, 07 May 2009 12:49:04 +0200

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

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

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:
subst(Px, x, a);
%1 = 30

same 2-polynomial efficiently coded as vector:
res=0;for(i=1,length(qPx),res+= qPx[i] * a^(2^(i-1)));
%2 = 30

1. Is there a more elegant way to work with q-polinomials in PARI?
2. Is there any other computer algebra system that can work natively
with q-polynomials (I couldn't find any)?
3. Would PARI be a "right" CAS to implement q-polynomials natively?

[Ore33] O. Ore. On a special class of polynomials. Transactions of the
American Mathematical Society, 35:559-584, 1933.

[LN84] R. Lidl, H. Niederreiter, Finite Fields. Cambridge, UK: Cambridge
Univ. Press, 1984.