#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, Simon King
Authors: John Perry | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Changes (by john_perry):
* reviewer: Andrey Novoseltsev => Andrey Novoseltsev, Simon King
Comment:
> > Replying to [comment:28 SimonKing]:
> 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.
The only part that surprises me is that items with the same hash are put
into a bucket. I had learned hashes differently.
> 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 see; the hash has been broken a while. I can suggest a quick hash
function, actually: compute a Groebner basis of the ''homogenized'' ideal
'''up to degree''' ''d'' for some small value of ''d''. (Standard
homogenization, if there's any doubt.)
Figuring out a good value of ''d'' would be the hard part. If it's fixed
at a constant, the worst you'd see is a bunch of ideals in the same
bucket, which would force more Groebner basis computations than one would
like. Alternately, ''d'' could be computed based on the generators, though
I'm not sure how to do that quite yet. (max degree + 1? could get very,
very expensive for some ideals)
This seems to me the safest way to provide a relatively quick signature
for an ideal that ensures equal ideals with different presentations are in
the same bucket, at the cost of several distinct ideals sharing the same
bucket.
> 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.
This strikes me as a significantly different problem, albeit related,
deserving of its own ticket.
> > 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.
I wasn't thinking of eliminating a a ''default'' ordering for a ring that
extends automatically to its ideals; that makes sense. I would just like
the option to switch the default ordering of a ring or ideal, without
having to create a new ring and/or ideal, ''and'' retaining the
previously-computed Groebner basis, if desired.
This annoyance has actually come up in my work. I suspect a fix would
require a serious re-thinking, since so many things rely on Groebner
bases, and many have likely been written with the current framework in
mind. It may not be feasible in the short term, maybe not even in the long
term, but it seems worth discussing.
> 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.
Can you point me to a thread or ticket?
BTW, I'm adding you as a reviewer.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12802#comment:32>
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.
