Hi, On Thu, Aug 05, 2010 at 06:04:34PM -0600, Aaron S. Meurer wrote: > > On Aug 5, 2010, at 5:45 PM, Mateusz Paprocki wrote: > > > Hi, > > > > On Thu, Aug 05, 2010 at 05:09:26PM -0600, Aaron S. Meurer wrote: > >> I didn't want to open an issue before asking here, because for all I know > >> there could be a very good reason for this. > >> > >> In [1]: Poly(-5*x**3, x).div(Poly(3*x, x)) > >> Out[1]: (Poly(0, x, domain='ZZ'), Poly(-5*x**3, x, domain='ZZ')) > >> > >> In [2]: Poly(-5*x**3, x, field=True).div(Poly(3*x, x, field=True)) > >> Out[2]: (Poly(-5/3*x**2, x, domain='QQ'), Poly(0, x, domain='QQ')) > >> > >> I understand that it doesn't want to create field coefficients, but I > >> thought that the definition of polynomial division and remainder was that > >> a.div(b) returns q and r such that a == b*q + r and **either r == 0 or > >> deg(r) < deg(b)**. [1] obviously does not satisfy this second condition. > >> So what definition does it use? > >> > >> This is causing problems in the Risch algorithm. It seems like I need to > >> be using field=True every time I create a Poly, or else I will get wrong > >> results. But then that gives things like gcd() problems. > >> > >> By the way, I know about pdiv. But I think regular div() should be > >> returning results with field coefficients if it must to satisfy the > >> definition, unless I am seriously missing something. > >> > > > > The conditions are met only over a field or when b is monic. Over > > integers with non-monic b you arrive with the problem you showed. > > If you rely on those conditions (e.g. you are creating a sequence > > of polynomials with decreasing degrees) then you have to perform > > computations over a field (unless your polynomials are monic --- > > not a very interesting case in general). > > > > I guess you run into this problem somewhere around EEA (Extended > > Euclidean algorithm). In this case (and a few other, e.g. Strum > > sequences) user-level polynomial manipulation functions switch > > ground domain to a field automatically (on lower levels you get > > DomainError exception to avoid infinite loops). > > > > So, you will have to use field=True whenever the conditions must > > be met. We may also think about adding this automatic behaviour > > to div() (as it is done in gcdex(), half_gcdex(), sturm() …). > > I guess I will just use field=True. Maybe there should be a field option to > div. > I do think that user level functions should be assuming a field ground domain > by default, unless they are instructed to do otherwise. >
We have played this game from the very beginning: different problems to solve, different visions on where which classes of domains should be used. If you would use field every where then you would solve your problem, but create other, e.g. with GCD. The approach in polys is simple: use the smallest domain when it makes sense; if it doesn't then raise an exception or automatically enlarge the initial domain. If you need better control on what happens, then you have a variety of options and flags available. > > > > You said that there are problems with gcd() computations. What > > is specifically wrong here? Maybe it's an issue that GCD over > > a field is always monic in SymPy? > > Yeah that's basically the problem. splitfactor() uses gcd() to split a > function into normal and special parts (like splitter() in heurisch), but it > only splits apart the coefficients correctly if it takes the ring gcd. Maybe > there's a better solution, but right now I have had to take the gcd with > respect to each coefficient and its inverse, such as x and 1/x. I think I > tried using a similar method as splitter, with the loop, but it didn't work. > This was all a while ago, so I am not remembering the details the best. > Maybe I need to revisit the problem. > Here is a trivial example: In [1]: cofactors(2*x**2 - 2, 4*x - 4) Out[1]: (-2 + 2⋅x, 1 + x, 2) In [2]: cofactors(2*x**2 - 2, 4*x - 4, field=True) Out[2]: (-1 + x, 2 + 2⋅x, 4) So, in [1] the common content is kept in the GCD, whereas in [2] it is not. What happens over a field, is that in general we don't know how to 'simplify' a sequence of elements of the ground domain, so the simplest and the most consistent way is to simply make the GCD monic. Some systems try to be clever, e.g. Mathematica, and return non-monic results (e.g. make cofactors' coefficients elements of a ring -> clear denominators of cofactors; and use common content removal for numerators), whereas others, like Axiom, are pedantic. We can implement Mathematica's approach in SymPy (usable by setting a flag in gcd()'s or cofactors()'s keyword arguments). > Aaron Meurer > > > > >> Aaron Meurer > >> > >> -- > >> You received this message because you are subscribed to the Google Groups > >> "sympy" group. > >> To post to this group, send email to sy...@googlegroups.com. > >> To unsubscribe from this group, send email to > >> sympy+unsubscr...@googlegroups.com. > >> For more options, visit this group at > >> http://groups.google.com/group/sympy?hl=en. > >> > > > > -- > > Mateusz > > > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to sy...@googlegroups.com. > To unsubscribe from this group, send email to > sympy+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- Mateusz
signature.asc
Description: This is a digitally signed message part