#12802: test containment of ideals in class MPolynomialIdeal
--------------------------------------------------+-------------------------
Reporter: mariah | Owner: AlexGhitza
Type: enhancement | Status: needs_info
Priority: minor | Milestone: sage-5.1
Component: commutative algebra | Resolution:
Keywords: sd40.5, groebner bases, ideals | Work issues: cache
handling
Report Upstream: N/A | Reviewers: Andrey
Novoseltsev
Authors: John Perry | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Changes (by SimonKing):
* cc: nthiery (added)
Comment:
Replying to [comment:30 john_perry]:
> Replying to [comment:28 SimonKing]:
> > Compare #12976: If you work on comparison of ideals, you should
perhaps also consider the fact that ideals evaluating as equal may have
different hash, because the hash relies on the string representation
(hence, on the generators), but the comparison relies on Gröbner bases.
So, the hash is broken (and is rather slow, too).
>
> I don't understand the issue with the hash, probably because I don't
know anything about how Sage hashes rings, ideals, etc.
That's how Python uses the hash: Python's dictionaries and sets are hash
tables. Hence, whenever you use an ideal J (or any other object) as a key
in a dictionary D or put it into a set S, then the hash is computed, and
the object is put into a "bucket" that corresponds to the hash value.
If you then have an object G (say, the ideal that is given by the reduced
Gröbner basis of J) and want to test whether G is in D or S (say, `D[G]`
or `G in S`), then the hash of G is computed, and then '''only the bucket
corresponding to the hash of G''' is searched for an equal object. The
buckets typically are very small. Hence, if you have a quick hash function
then searching in a set is much faster than searching in a list.
Now, a problem arises if `G==J` but `hash(G)!=hash(J)`: G and J may end up
in ''different'' buckets, and thus `G in S` would return False, even
though `J in S and J==G`.
Summary: It is required by Python that the hash values of equal objects
are equal. Otherwise, the hash is called "broken".
> I can look into this, but: the code ignores the hash altogether, and a
Groebner basis is only computed for a copy; the original ideal is
untouched. So, how could this patch break the hash?
I did not claim that the patch breaks the hash. I merely stated that the
hash '''is''' broken (see #12976), and I asked whether we should extend
the patch here so that the hash is fixed, or whether we leave the hash
broken for now.
> When I run the example you provide in #12987, I get this:
> {{{
> sage: %timeit J==J2
> 5 loops, best of 3: 534 ms per loop
> sage: _ = J.groebner_basis()
> sage: %timeit J==J2
> 5 loops, best of 3: 533 ms per loop
> sage: _ = J2.groebner_basis()
> sage: %timeit J==J2
> 5 loops, best of 3: 533 ms per loop
> }}}
> So it's even worse than you say; it's not that I didn't fix it; I've
actually broken something there. (I don't think this is the hash; correct
me if I'm wrong.)
No, there is no hash involved here.
> IMHO, rings and ideals ought to be independent of term orderings, which
the user ought to be able to switch without creating a new ring & ideal.
That sounds nice at first glance. However, it would be awkward to ask for
providing a term order as a new argument to the groebner_basis() method.
And there are many algorithms that rely on Gröbner bases. So, I believe
having a default term order for each ring (and thus have different rings
for different term orders) is fine, IMHO.
Anyway, ideals that are independent of a default term order could probably
be implemented using the "parents with multiple realisations" that have
recently been introduced (hence, Cc to Nicolas...). I wonder, though, if
that would be possible without a speed regression.
> But, your proposal:
>
> > One could create an attribute `_gb_by_term_order_` that is a
dictionary storing the Gröbner bases of an ideal with respect to different
orders.
>
> ...seems similar. Do you think a long-term fix of making rings
independent of term orderings would be worth looking at?
I am not sure, see above.
> > How should one proceed? Fix the "useless double-computation of Gröbner
bases of copies of ideals" here? Then this ticket is "needs work", and
#12987 is a duplicate. Or fix it at #12987? Then I have to add this ticket
as a new dependency for #12987.
>
> I think it better to mark #12987 as a duplicate in that case, the same
way #12839 is a duplicate, and fix this issue here, at least with your
proposed approach. I can certainly do that.
OK, I'll comment #12987 accordingly.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12802#comment:31>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
