[GAP Forum] manipulating polynomials

[Alexander Hulpke]

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