[GAP Forum] manipulating polynomials

[Iulian Simion]

Dear Forum, Dear Jakob, Dear Alexander,

I had some experience with polynomials in GAP (situations where one
considers several polynomial rings with a lot of variables, polynomial
rings over polynomial rings, etc) and had to implement my one set of
functions for polynomial manipulations.

The way I see it, the main difficulty is that the ExtRepPolynomialRatFun,
the implemented representation of polynomials, seems to label all
indeterminates of all polynomial ring instances with integers in some
common global list which stacks up during the lifetime of a GAP instance.
This has probably good performance reasons and is in my opinion the main
reason why one has to go through some tedious book-keeping for good
implementations of additional functionality.

There is already PositionSorted which searches through a sorted list. Then
the function CoefficientOfPolynomial could be a bit shorter:

InstallMethod(CoefficientOfPolynomial,"search in sorted
extrep",IsIdenticalObj,
  [IsPolynomial,IsPolynomial],0,
  function(pol,mon)
  local ep,em,pos;

  ep:=ExtRepPolynomialRatFun(pol);
  em:=ExtRepPolynomialRatFun(mon);
  if Length(em)<>2 or not IsOne(em[2]) then Error("second parameter must be
monomial"); fi;

  # using PositionSorted (assuming the ext-rep is sorted)

pos:=PositionSorted(ep{2*[1..Length(ep)/2]-1},em[1],FamilyObj(pol)!.zippedSum[1]);

  if ep[2*pos-1]=em[1] then return ep[2*pos];
  else return fam!.zeroCoefficient; fi;
end);


I have many good reasons why I am using GAP but polynomial manipulation is
not something the system aims at (at the moment?). I think GAP would have a
good chance for fast polynomial manipulations but this would required (as
already mentioned) some extensive implementation and probably a rethinking
of the Polynomial data structure.

all the best,
Iulian


On Sun, Sep 23, 2012 at 9:10 PM, Alexander Hulpke <ahulpke at gmail.com> wrote:

> 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 <kroeker at 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: hulpke at math.colostate.edu, Phone: ++1-970-4914288
> http://www.math.colostate.edu/~hulpke
>
>
> _______________________________________________
> Forum mailing list
> Forum at mail.gap-system.org
> http://mail.gap-system.org/mailman/listinfo/forum
>