Post new topic Reply to topic  [ 5 posts ] 
Author Message
 Post subject: Testing divisibility of multivariate polynomials
PostPosted: Wed May 04, 2016 3:55 pm 
Is there a function to test whether a (multivariate) polynomial f divides another polynomial p? Of course, one can compute the reduction of p modulo f. As it happens, for many variables and fairly sparse p (and quite simple f, say of total degree 1 for instance), computing the reduction is pretty fast when f does divide p, but may take a very long time if f does not divide p. (I have the impression that this is due to the fact that p%f can be very dense in such case.) Actually, in case f does not divide p, one can often give the answer very early (as soon as one begins to "fill" the remainder). So my question: Is there a function in Singular which implements this (fairly trivial and naive) optimization?

P.S.: I use Singular through Sage. In Sage, the method f.divides(p) simply calls p%f and tests it for zero. If a function as I ask for exists in Singular, I'll do my best to use it in the method "divides" of Sage.


Report this post
Top
  
Reply with quote  
 Post subject: Re: Testing divisibility of multivariate polynomials
PostPosted: Fri May 06, 2016 12:38 pm 

Joined: Wed May 25, 2005 4:16 pm
Posts: 178
see
http://www.singular.uni-kl.de/Manual/4-0-3/sing_383.htm.
For such tests use
Code:
reduce(p,f,1)

which computes only the leading term of p%f completely,
usually much faster if only the divisibility test is needed.


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Testing divisibility of multivariate polynomials
PostPosted: Mon May 09, 2016 4:13 pm 
Thanks for the pointer. I have trouble to find the source code corresponding to this function, do you have any hint?


Report this post
Top
  
Reply with quote  
 Post subject: Re: Testing divisibility of multivariate polynomials
PostPosted: Tue May 10, 2016 10:19 am 

Joined: Wed May 25, 2005 4:16 pm
Posts: 178
for version 3-1-7:
reduce is internally
Code:
poly kNF (ideal F, ideal Q, poly p,int syzComp=0, int lazyReduce=0);

from kernel/kstd1.cc, i.e. one have to use (the additional argument 1 maps to lazyReduce)
Code:
result=kNF(<f converted to ideal>,NULL,p,0,1)

Analog for version 4-0-3: kNF is now in kernel/GBEngine/kstd1.cc


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: Testing divisibility of multivariate polynomials
PostPosted: Wed May 11, 2016 2:59 pm 
Thank you very much. I implemented a method `divides` for multivariate polynomials in Sage based on kNF. See ticket #20588.


Report this post
Top
  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 5 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 Mon Dec 18, 2017 9:16 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group