Singular
https://www.singular.uni-kl.de/forum/

p-th powers in characteristic p
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2055		 Page 1 of 1
Author:  edward [ Sun Feb 12, 2012 1:19 am ]
Post subject:  p-th powers in characteristic p
Hi!

I am doing some calculations that involve taking very large polynomials and raising them to p-th powers in a field with characteristic p. The length of time it is taking leads me to believe that Singular is not using the fact that (x+y)^p = x^p + y^p in char p.

Is there some library or easy way to get Singular to do p-th powers of a polynomial in char p?

Thanks so much!

Edward
Author:  steenpass [ Mon Feb 13, 2012 8:26 am ]
Post subject:  Re: p-th powers in characteristic p
Hi,

as far as I know, you're right, Singular doesn't use this fact and there is no built-in command nor library to compute such powers in the way you want. But it is easy to write such a procedure:

Code:
proc toThePowerOfChar(poly f)
{
  poly g;
  int p = char(basering);
  int i;
  for(i = size(f); i > 0; i--)
  {
    g = g+f[i]^p;
  }
  return(g);
}


This speeds up the computation a lot:

Code:
> system("--ticks-per-sec", 1000);
> ring r = 1009, (x,y,z), dp;
> poly f = x+y+z;
> int t = timer;
> f^char(basering);
x1009+y1009+z1009
> timer-t;
18650
> t = timer;
> poly h = toThePowerOfChar(f);
> timer-t;
10


Of course, it depends on your applications whether or not this helps in your case.

Best regards,
Andreas
Author:  gorzel [ Mon Feb 13, 2012 3:49 pm ]
Post subject:  Re: p-th powers in characteristic p
In your particular, where case char(basering)=p>0, it holds:

raising the polynomial f to the p-th power commutes with
raising the variables to the p-th power.

This is, f^p is obtained instantly by:
Code:
> int p = char(basering);
> subst(f,x,x^p,y,y^p,z,z^p);

(In any case, at most, you have to cycle in a for-loop over var(1),...,var(n),
n=nvars(basering) but not over the single terms N=size(f)).

Don't care too much about the warnings (about possible overflow in the expont) which may appear.
(The warning refers to the total degree but not to the degree of the individual variables.)

You may also use the command substitite, which can be used for simultaneous substitution.
Here (at the moment) the warning does not occur.
Code:
> LIB "poly.linb";
> substitute(f,maxideal(1),ideal(x^p,y^p,z^p));

However, if your polynomial is huge with respect to the number of
monomials, then substitute may be a bit slower than subst,
since substitute is a proc and for this function-call the input
will be copied. If this is critical for you, then use map directly as substiute does.
Author:  edward [ Mon Feb 13, 2012 5:45 pm ]
Post subject:  Re: p-th powers in characteristic p
Thanks steenpass and gorzel, this helps a lot!

Edward
Author:  gorzel [ Mon Feb 13, 2012 11:47 pm ]
Post subject:  Re: p-th powers in characteristic p
In my answer I made the assumption that, as in the examples, the coefficients are 1.
Otherwise, it does not work in general as I proposed.
Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/