Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: Large powers of polynomials in small characteristic
PostPosted: Tue Apr 05, 2016 7:33 pm 

Joined: Mon Sep 22, 2008 1:07 am
Posts: 3
Back in 2009, there was discussion on the Sage developers mailing list:

https://groups.google.com/forum/#!topic ... MPWGadoSpA

about the fact that in a multivariate polynomial ring of very small characteristic, raising a polynomial to a large power was being done suboptimally. Namely, one should really account for the fact that in characteristic p, raising to the p-th power acts on individual monomials; so to compute f^n, one ought to write n = a_0 + a_1 p + a_2 p^2 + ... and compute f^n as f^a_0 * (f^p)^(a_1) * ...

I just repeated the timing test from that thread, and as of 2016 it is still possible to do much better than what is implemented by explicitly splitting the exponent into base-p digits. It appears that the underlying representation of these polynomials is in Singular, so maybe the discussion should be continued here.

To make a particularly egregious example:

int p = 7;
ring rp = p, (x,y,z), dp;
poly f = (x^3 + y*z + z + y*y + x*z)^4;
poly g= f^(p^2);

should return instantaneously; instead, it takes about 10 seconds on my laptop.

Kiran


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Large powers of polynomials in small characteristic
PostPosted: Wed Apr 06, 2016 3:47 pm 

Joined: Wed May 25, 2005 4:16 pm
Posts: 178
Thanks for the hint, I added the handling of this special case
(see https://github.com/Singular/Sources/commit/6538bdbf4f61760cc2956dcad64e92c75f6531e6)


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Wed Dec 13, 2017 8:32 pm
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group