On Aug 28, 1:21 pm, Sebastian Pancratz <s...@pancratz.org> wrote:
> On Aug 27, 1:00 pm, luisfe <lftab...@yahoo.es> wrote:
>
> > I have added a new ticket for adding a default gcd and lcm for field
> > elements.
>
> >http://trac.sagemath.org/sage_trac/ticket/9819
>
> > For the case of field elements gcd and lcm methods are not of great
> > interest. However, they can be addecuated for some reasons.
>
> > - Some algorithms may accept as input either polynomials or rational
> > functions. In these algorithms we may reduce a list of polynomials and
> > rational functions to a common denominator. If all the inputs are
> > polynomials, the denominators are the one element of the base field.
> > In this case, lcm would fail.
>
> I just briefly want to point out that this is not true (e.g.
> polynomial over the rationals, instead of finite fields). For
> example,
>
> sage: R.<t> = QQ[]
> sage: f = 1/3 + x/5
> sage: f.denominator()
> 15
>
> Here f is a polynomial and f.denominator() gives the least common
> multiple of the denominators of the coefficients. On the technical
> side, here f simply isn't an element of a fraction field and hence the
> denominator() method is not meant to return the denominator of a
> fraction field element. Note that, I hope quite obviously, the notion
> of the "denominator" of a polynomial over a fraction field makes
> sense, although it is implemented here for polynomial rings over Q
> rather than any such polynomial ring.
>
> For comparison,
>
> sage: S = Frac(R)
> sage: S(f).denominator()
> 1
>
> Here, denominator() is the method for rational functions over Q.
> Fortunately, 1 and 15 are the same up to multiplication by units in
> the rationals and everything is fine.
you are right, it will work as long as the base ring have a lcm
function.
> --- Actually, let me give a short aside. The construction mentioned
> above, that is, polynomial rings R over fraction fields F of a ring K,
> isn't yet handled separately in Sage. After having worked on
> polynomial rings over Q and rational functions over Q, I think this
> would help a lot. For example, it would allow for an implementation
> of the field of rational functions (elements in the fraction field of
> R) not as a fraction field of R but as the fraction field of the ring
> of polynomials over K (instead of F). Incidentally, in the example
> above, if Frac(QQ[]) was implemented as Frac(ZZ[]), the second example
> might reasonably result in the answer 15, too. ---
The difference in this case is that the denominator would be a
polynomial instead of an element of the base ring. With the actual
implementation, for a polynomial f, it should be that f.numerator()/
f.denominator() is a polynomial equal to f. With the alternative,
f.numerator()/f.denominator() would be a rational function equal to f.
I can imaging users expecting one result or the other depending on the
situation.
> > See the problem raised in #9063 for a case of this problem.
>
> > I propose to add a lcm and gcd funtion for field elements.
>
> > By default, if both elements are zero, their gcd is 0. Otherwise 1
>
> > if one of the elements is zero, their lcm is zero. 1 Otherwise.
>
> > However, I can imaging that this approach may lead to further
> > problems. Does anyone have a case where this approcah can lead to
> > problems?
>
> > Luis
>
> The main problem with GCDs and LCMs, as far as their implementation is
> concerned, is that they are only defined up to units. Thus, as choice
> *must* be made in the underlying implementation. However, this does
> *not* mean that calling methods always have to rely on a specific
> choice. In fact, in particular for a system as large and quickly
> changing as Sage, the code will be a lot more robust if calling
> methods choose to not depend on such choices.
I agree with that, the algorithms using gcd and lcm output should not
be expected to be on a specific choice of the unit if possible.
> --- This might all sound as if I've copied this out of some design
> pattern book and as if it's completely irrelevant in practice.
> Actually, it's not :(. When working on univariate polynomials over
> the rationals in #4000, I ran into a more than a handful of such
> problems. For example, the normalisation of the greatest common
> divisor wasn't the same in gcd and xgcd. Moreover, the normalisation
> of the greatest common divisor wasn't obvious. There are two obvious
> choices, namely either monic or primitive over Z with positive leading
> coefficient, where the first choice is often mathematically convenient
> and the second one is closer to the implementation at hand now. The
> choice in the old implementation was something like the first, except
> that something like gcd(self, 0) would return self to shave of some
> speed in that special case, neglecting that self might not be monic.
> Of course, all of these issues carry over to the implementation of
> lcm. And finally, to make matters worse, some other code
> (mathematically relevant, as opposed to, say, pretty printing of
> rational functions) in the Sage library depended on this specific
> choice for correctness. ----
Yes, this is a problem.
> Is it worth that once and for all we try to force a specific choice
> across all field implementations? I don't think so.
I would not like that neither.
> You could try to argue that there's nothing wrong with implementing a
> generic choice (the one you outlined!) for all fields now, and then
> specific fields might be allowed to overwrite this method later.
> However, so long as calling methods (taking any field elements as
> input) actually depend on the specific choice you fix generically,
> this doesn't help and brings us right back to this discussion.
That would be my answer indeed. I still think that there should be a
fallback implementation of lcm but I see the problem, calling methods
that depend on a specific shape of a gcd/lcm (ex. monic polynomials)
are not bug free because they will fail if the gcd/lcm is not in that
shape (because the function has been overwritten somewhere, this is
specially the case if QQ is involved). On the other hand, if on every
calling method rewrite the gcd/lcm on a specific shape, this would
yield to an undesirable overhead.
For instance in structure/element_base.pyx a _lcm for FieldElement is
already there with the same defaults as above, but nobody has written
a lcm function that is coercion-aware for FieldElement.
Furthermore, appart from the field case, lcm is broken from the point
of view of the coercion model, the gcd seems more robust to me. The
lcm has to be changed in any case.
{{{
sage: gcd(ZZ(4),QQ(4))
1
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: lcm(ZZ(4),QQ(4))
4
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: lcm(QQ(4),ZZ(4))
...
TypeError: Argument 'other' has incorrect type (expected
sage.rings.rational.Rational, got sage.rings.integer.Integer) # not ok
sage: lcm([QQ(4),ZZ(4)])
4
sage: type(_)
<type 'sage.rings.rational.Rational'> #ok
sage: x=QQ[x](x)
sage: lcm(x, ZZ(4))
x
sage: lcm(x, QQ(4))
...
RuntimeError: Singular error: #not ok
}}}
Best,
Luis
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
