#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:
--------------------------------------------------+-------------------------
Comment (by john_perry):
Replying to [comment:33 SimonKing]: I am not a computer scientist, either.
I learned that each hash corresponds to one, unique element. When clashes
occur, the second element to hit the hash is given a new hash, based on a
certain heuristic.
My understanding of what you wrote is that several objects can occupy the
same hash value, and when comparisons need to be made, something more
computationally expensive is called: `__eq__`, perhaps. (I wasn't sure
exactly which.) That strikes me as what
[http://wiki.python.org/moin/DictionaryKeys this page] is saying, too,
though I am not entirely sure.
> > 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.)
> Wouldn't that, again, depend on the term order?
We'd have to pick a "good" term order for the hash, just as we currently
pick a "good" term order to test whether ideals are equal, if no Groebner
basis currently exists.
> And how should one choose '' d'' ? After all, if you compute a Gröbner
basis out to degree '' d'' but there are further elements in higher
degree, then the '' complete'' Gröbner basis will have a different hash.
Well, yes, I said that, myself. My idea gets pretty bad, pretty quickly: A
nice example of how things can go wrong is if I=<x,x^5^+x+1> and
J=<x^5^+1,x^5^+x+1>, which are equal (to <1>, in fact). But the
homogenized ideals' Groebner bases are different, regardless of degree. If
one dehomogenizes, it works out, but this is already getting pretty ugly.
> Perhaps one could make ideals non-hashable?
I'm okay with that, too. Are ideals mutable? If so, the answer is easy.
To my thinking, ideals *are* hashable in principle; just use a Groebner
basis wrt to any order at all. It's the computation of the hash that's
potentially horrifying. Do you know if Python calls `__hash__` when the
ideal is created, or when it's actually required? If it's the latter,
rather than the former, we could simply compute a hash by computing the
degrevlex Groebner basis, and be done with it. No one would encounter the
performance penalty until they actually tried to use it.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12802#comment:34>
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.
