Dear Forum, Dear Jakob Kroeker,
The following will be in parts a rather technical response. The executive
summary is that GAP sometimes has to do tradeoffs that make its internal data
types not perfect for all occasions, but that there are also a multitude of
functions to interact with these data types that can be of help.
On Sep 23, 2012, at 7:59 AM, kroeker <kroe...@uni-math.gwdg.de> wrote:
> The core GAP polynomial manipulation function set is sufficient but very
> basic. Extensive polynomial manipulation using ExtRepPolynomialRatFun would
> be very tedious and computationally expensive
> ( e.g. coefficient access compexity) and I experienced this in a recent join
> project to compute Hurwitz map approximations.
>
> An example and working definition for 'ConstantTerm' and
> 'CoefficientOfPolynomial' is attached.
I'm the first one to admit that the polynomial arithmetic in GAP is not as fast
as that in a dedicated ``polynomial'' system. However also a reasonable amount
of care has gone into it and it would not be trivial to rebuild equivalent
functionality from scratch.
A function to access individual coefficients is probably useful for multiple
users and I will see to add it to the next version of GAP.
However your approach (storing the polynomial a second time in a dictionary) is
unnecessarily memory intensive, and (as I believe sorted lists are used inside
this type of dictionary anyhow) can be easily be improved upon by doing a
binary search directly through the (sorted! polynomials in GAP assume that the
terms are stored sorted and if not could produce arithmetic errors!)
coefficients. Concretely, I would expect the function
InstallMethod(CoefficientOfPolynomial,"binary search in extrep",IsIdenticalObj,
[IsPolynomial,IsPolynomial],0,
function(pol,mon)
local a,b,fam,ep,em,cmp,mid;
fam:=FamilyObj(pol);
ep:=ExtRepPolynomialRatFun(pol);
em:=ExtRepPolynomialRatFun(mon);
if Length(em)<>2 or not IsOne(em[2]) then
Error("second parameter must be monomial");
fi;
em:=em[1];
# binary search in steps of 2 -- this could be in the kernel to be faster
cmp:=fam!.zippedSum[1]; # monomial comparison function
a:=1;
b:=Length(ep)-1;
while a<b do
mid:=a+2*QuoInt(b-a,4);
if cmp(ep[mid],em) then
a:=mid+2;
else
b:=mid;
fi;
od;
if a=b and ep[a]=em then
return ep[a+1];
else
return fam!.zeroCoefficient;
fi;
end);
to perform as well as the one you proposed while avoiding the storage
duplication.
I'm a bit reluctant to add ``personal convenience'' functions (such as ``more
handy format for factors'') to the main GAP system as this likely is dependent
on personal preference.
> (e.g. evaluating/differentiating a polynomial tensor,
You are aware of `Derivative'?
> coercing polynomials to different rings,
Polynomials don't belong to a ring but to a coefficients family. If you want to
transfer between finite characteristic and characteristic zero, care has to be
taken that the ``right'' interpretation for finite field elements is chosen,
e.g. do you want -p/2..p/2 or 0..p-1?
> counting variables appeared in a polynomial,
There is OccuringVariableIndices from which the number is easily deduced.
I realize that not all of this is documented in the manual. If you need a
specific function or information about a particular library function please
feel free to ask.
Best,
Alexander Hulpke
-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hul...@math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
_______________________________________________
Forum mailing list
Forum@mail.gap-system.org
http://mail.gap-system.org/mailman/listinfo/forum
