# Singular

 Page 1 of 1 [ 5 posts ]
 Print view | E-mail friend Previous topic | Next topic
Author Message
 Post subject: Testing divisibility of multivariate polynomialsPosted: 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.

Top

 Post subject: Re: Testing divisibility of multivariate polynomialsPosted: Fri May 06, 2016 12:38 pm

Joined: Wed May 25, 2005 4:16 pm
Posts: 205
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.

Top

 Post subject: Re: Testing divisibility of multivariate polynomialsPosted: 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?

Top

 Post subject: Re: Testing divisibility of multivariate polynomialsPosted: Tue May 10, 2016 10:19 am

Joined: Wed May 25, 2005 4:16 pm
Posts: 205
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

Top

 Post subject: Re: Testing divisibility of multivariate polynomialsPosted: 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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

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

 It is currently Tue Oct 16, 2018 12:10 am