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.
--- 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. ---
> 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.
--- 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. ----
Having said that, as far as correctness and robustness are concerned,
it's clear that the calling method simply should only expect some
greatest common divisor, rather than a specific one. Thus, the focus
now shifts to speed.
In light of #9063, yes, it would be very convenient if gcd(x,y) for a
pair of field elements (x, y) not equal to (0, 0) returns 1. But it's
completely feasible that other, perhaps even more low-level
implementations, might benefit (in terms of speed) from another
arbitrary choice.
Is it worth that once and for all we try to force a specific choice
across all field implementations? I don't think so.
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.
Best wishes,
Sebastian
--
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
