#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 SimonKing):
Replying to [comment:34 john_perry]:
> 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.
Yes.
> > Perhaps one could make ideals non-hashable?
>
> I'm okay with that, too. Are ideals mutable? If so, the answer is easy.
I don't think they are mutable.
> 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.
Yes, that's exactly the problem. One can compare ideals and can compute a
reasonable hash effectively, but probably there is no way to do that
efficiently in a way that preserves the mathematical notion of equality of
ideals (namely: Equality as a sub-set of a ring).
> Do you know if Python calls `__hash__` when the ideal is created, or
when it's actually required?
No. The hash is only computed when it is needed (hence, when the ideal is
put into a set or dictionary). The following toy example should illustrate
what is called when:
{{{
sage: class Foo:
....: def __init__(self, n):
....: self.n = n
....: def __hash__(self):
....: print "computing hash for",self.n
....: return int(self.n%10)
....: def __cmp__(self, other):
....: print "comparing",self.n,"with",other.n
....: return cmp(self.n, other.n)
....:
sage: a = Foo(5)
sage: b = Foo(6)
sage: c = Foo(15)
sage: a2 = Foo(5)
sage: a == a2
comparing 5 with 5
True
sage: a == b
comparing 5 with 6
False
sage: D = {}
sage: D[a] = 1
computing hash for 5
sage: D[a]
computing hash for 5
1
sage: D[b] = 2
computing hash for 6
sage: D[c] = 5
computing hash for 15
comparing 5 with 15
}}}
As you can see in the last line, the hash of c is computed, which I made
coincide with the hash of a. So, they are put into the same hash bucket,
and thus a comparison happens. But the line before, no comparison happens,
because the hash bucket for b is empty when it is added to the dictionary.
In particular, normally the hash is not computed during initialisation.
However, due to caching a lot of stuff in the category and coercion
framework, it could very well be that the hash is created during
`__init__`. I don't think that is the case for ideals, though.
> 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...
... which is not unlikely. Currently, ideals ''are'' used in dictionaries,
for example in singular_function, when trying to convince Singular that
the given generators of some ideal form a Gröbner basis. That's why I try
to provide a faster (though syntactically less elegant) way to provide
information on the arguments of singular_function (see #12977).
I promised to provide you with a ticket number for multiple realisations:
#7980.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12802#comment:35>
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.
