Opened 10 years ago

Closed 9 years ago

test containment of ideals in class MPolynomialIdeal

Reported by: Owned by: mariah AlexGhitza minor sage-5.4 commutative algebra sd40.5, groebner bases, ideals malb, nthiery sage-5.4.rc0 John Perry Andrey Novoseltsev, Simon King N/A

There seems to be no way to test containment of ideals in the class MPolynomialIdeal in `sage.rings.polynomial.multi_polynomial_ideal`. One might expect the comparison operators (e.g. `I<J` ) to do this, but in fact what they do is to compare the Groebner bases as sequences of polynomials, which is counterintuitive. For example:

```sage: R.<x,y> = PolynomialRing(QQ)
sage: I=(x*y)*R; J=(x,y)*R; I<J
False
sage: I=(y+1)*R; J=(x,y)*R; I<J
True
```

This is implemented in the `__cmp__` method, which is not up to the task of doing subset comparison, since `__cmp__` is only suitable for total orderings.

To do it right would seem to require implementing Python's "rich comparison" methods, `__lt__`, `__gt__`, etc.

For example:

```from sage.rings.polynomial.multi_polynomial_ideal import MPolynomialIdeal

def IsSubset(I,J):
for g in I.gens()
if not g in J: return False
return True

def IsSuperset(I,J):
return IsSubset(J,I)

def IsProperSubset(I,J):
return I!=J and IsSubset(I,J)

def IsProperSuperset(I,J):
return I!J and IsSuperset(I,J)

setattr(MPolynomialIdeal,'__le__',IsSubset)
setattr(MPolynomialIdeal,'__lt__',IsProperSubset)
setattr(MPolynomialIdeal,'__ge__',IsSuperset)
setattr(MPolynomialIdeal,'__gt__',IsProperSuperset)
```

With these we now get the expected behavior:

```sage: R.<x,y> = PolynomialRing(QQ)
sage: I=(x*y)*R; J=(x,y)*R; I<J
True
sage: I=(y+1)*R; J=(x,y)*R; I<J
False
```

The patch supplied gives a solution via Groebner bases, and also fixes #12839.

Apply:

1. trac_12802_no_whitespace.patch

comment:1 Changed 10 years ago by john_perry

• Authors set to John Perry
• Description modified (diff)
• Keywords sd40.5 groebner bases ideals added
• Status changed from new to needs_review

The attached file gives a better check for correctness than even the proposed solution, using Groebner bases rather than generators alone. The examples given by mariah produce a correct result on my machine, though for a doctest I use a slightly different solution which her proposed fix wouldn't detect.

This patch also resolve #12839, as far as I can tell.

comment:2 follow-up: ↓ 3 Changed 10 years ago by novoselt

• Status changed from needs_review to needs_work
• Work issues set to documentation

Functions are missing standard documentation blocks.

comment:3 in reply to: ↑ 2 Changed 10 years ago by john_perry

Functions are missing standard documentation blocks.

It's even worse than that. For some reason, I'm now finding regressions that I didn't find earlier. I'm working on an updated patch.

comment:4 Changed 10 years ago by john_perry

Okay, so the problems were real, but were discovered because there's a very weird test of elements of quadratic number fields: basically, if a and b are distinct elements of a quadratic number field, then a>b and b>a are always true:

```sage: K.<a> = NumberField(x^2 + 1)
sage: a > a + 1
True
```

That strikes me as really, really odd behavior.

Anyway, I'm about to upload a new patch that undoes the stupidity I did to `sage.rings.ideal.py`, adds some documentation to the `__cmp__` function in `Ideal_generic`, then takes care of the things that need taking care of down in `sage.rings.polynomial.multi_polynomial_idea.py`. I've also added documentation. (Sorry about that -- it didn't occur to me because the stuff I was rewriting wasn't documented, either.) It also removes a boatload of whitespace.

comment:5 Changed 10 years ago by john_perry

• Reviewers set to novoselt
• Status changed from needs_work to needs_review

comment:6 Changed 10 years ago by john_perry

To help the reviewer(s), here are the non-whitespace changes.

1. In `sage/rings/ideal.py`, I added a docstring & doctest to `Ideal_generic`'s `__cmp__`.
2. In `sage/rings/polynomial/multipolynomial_ideal.py`, I
1. redefined `__cmp__` to rely on `__lt__`, `__gt__`, and `__eq__`;
2. changed `__eq__` to test whether each ideal is a subset of the other;
3. changed `__gt__` to test whether `other` is a subset of `self`; and
4. moved the old code for `__eq__` to `__lt__`, where it now checks whether each polynomial in the Groebner basis of `self` reduces to 0 modulo the Groebner basis of `other`. Here, I also had to move a `try...except` loop around, because of a strange `AttributeError` related to caching, raised only by the doctests of `pbori.pyx`.

On my machine all the doctests of `sage/rings` pass with this patch. I haven't doctested everything, though.

comment:7 follow-up: ↓ 8 Changed 10 years ago by novoselt

• Reviewers changed from novoselt to Andrey Novoseltsev

Would be better to have whitespaces separately... Anyway: "Decides whether two ideals are equal. The test is performed on the generators." does not sound right, this method does not decide whether ideals are equal. How about "Compare generators of two ideals." instead?

comment:8 in reply to: ↑ 7 Changed 10 years ago by john_perry

Would be better to have whitespaces separately...

I can do that, if you think it best. I'd rather not, now that I've removed them, but I can.

Anyway: "Decides whether two ideals are equal. The test is performed on the generators." does not sound right, this method does not decide whether ideals are equal. How about "Compare generators of two ideals." instead?

Done.

comment:9 Changed 10 years ago by novoselt

Apply trac_12802_and_12839.patch

comment:10 follow-up: ↓ 11 Changed 10 years ago by novoselt

• Status changed from needs_review to needs_work

I don't insist on separating whitespace patch now, it is just inconvenient to dig for changes in 100kb. But please make subsequent changes in a new little patch.

1. `__cmp__` does not return the result of self == other contrary to what is written. I also think that the test should call cmp directly, since `==` does not always lead to `cmp`.
2. In `__lt__` the documentation says "We use ideal membership to test whether the generators of each ideal appears in the other." while only one of the containment directions should be checked. Despite of the description of the algorithm in the documentation, the actual code does something else in the beginning and can return numbers or result of `cmp` instead of `True/False`.
3. What will `__cmp__` of ideals return if neither of them is contained in another? Do we even need it for ideals if there are lt/gt?
4. Documentation of `__eq__` is wrong.

comment:11 in reply to: ↑ 10 Changed 10 years ago by john_perry

I don't insist on separating whitespace patch now, it is just inconvenient to dig for changes in 100kb. But please make subsequent changes in a new little patch.

Okay, new patch coming. It'll be a bit.

1. `__cmp__` does not return the result of self == other contrary to what is written. I also think that the test should call cmp directly, since `==` does not always lead to `cmp`.

Got it.

1. In `__lt__` the documentation says "We use ideal membership to test whether the generators of each ideal appears in the other." while only one of the containment directions should be checked. Despite of the description of the algorithm in the documentation, the actual code does something else in the beginning and can return numbers or result of `cmp` instead of `True/False`.

This was originally code for `__cmp__`, and when I first started working on it, I had completely forgotten that `__cmp__` doesn't work the same as these other special functions. That was one reason for the regression I encountered earlier.

1. What will `__cmp__` of ideals return if neither of them is contained in another? Do we even need it for ideals if there are lt/gt?

When I first worked on this, the `__cmp__` of `Ideal_generic` was trumping everything else. That's why I redefined `__cmp__`, and it's also why I originally did some of this in `Ideal_generic`.

1. Documentation of `__eq__` is wrong.

It took me a while to find what you meant, but I finally saw it.

comment:12 Changed 10 years ago by john_perry

The last line in this `if` statement that you pointed out:

```        if R is not S: # rings are unique
if type(R) == type(S) and (R.base_ring() == S.base_ring()) and (R.ngens() == S.ngens()):
other = other.change_ring(R)
else:
return cmp((type(R), R.base_ring(), R.ngens()), (type(S), S.base_ring(), S.ngens()))
```

strikes me as wrong. If the base ring or the number of generators are different, they can't be the same ideal. I'm changing that to return `False`.

The type is another story. If someone has defined a ring with singular, and wants to compare to a ring defined with cocoa or macaulay, that ought to be possible. Unfortunately, I can't test it: neither Macaulay nor CoCoA build on my Sage 5.0. Are you able to build either?

comment:13 follow-up: ↓ 14 Changed 10 years ago by novoselt

I think comparison of rings should be done by converting all to a single system where they will be unique. And in general what's the point in ring uniqueness if they may not be unique? If you are not satisfied with `R is S` check, use `R == S` and let the meaning of this be handled by ring code, not the ideal comparison.

Note also that there are many failing doctests, the worst ones are with infinite recursion. If it will be necessary to change output in doctests of toric varieties, please do it on top of #13023 which is already positively reviewed.

comment:14 in reply to: ↑ 13 Changed 10 years ago by john_perry

I think comparison of rings should be done by converting all to a single system where they will be unique.

This has to be checked, due to different term orders. I've encountered regressions because of this; they may be the cause of some of your failing doctests.

Note also that there are many failing doctests, the worst ones are with infinite recursion.

I think I've fixed this one, too; I think the cause was related to returning numbers. I'm about to upload a new patch.

I wasn't getting any failures in `sage/rings`, btw, so I guess your failures are elsewhere?

comment:15 follow-up: ↓ 16 Changed 10 years ago by novoselt

I looked at the patchbot log (accessible through the disk in top right corner of the description).

comment:17 Changed 10 years ago by john_perry

At least some of those tests have nothing to do with this patch; I get them even when I pop & rebuild.

Edit: I forgot that there are two patches involved. They may be due to this after all; I'm looking at them now.

The toric_ideals.py regressions are already fixed.

Last edited 10 years ago by john_perry (previous) (diff)

comment:18 Changed 10 years ago by john_perry

Okay, it looks like I have a new patch ready. The problem was that lots of things depended on the old mpolynomial_ideal `__cmp__` as it was, and I had inadvertently broken that by tying it to subsets (for less than & greater than) rather than equality and non-equality. Those six tests now pass for me.

Updated patch on its way... I also fixed something in the documentation of `ideal`'s `__cmp__`.

comment:19 Changed 10 years ago by john_perry

• Description modified (diff)
• Status changed from needs_work to needs_review

comment:20 follow-up: ↓ 21 Changed 10 years ago by novoselt

• Status changed from needs_review to needs_work
```Rx = PolynomialRing(QQ, 2, "x")
Ix = Rx.ideal(Rx.0)
Ry = PolynomialRing(QQ, 2, "y")
Iy = Ry.ideal(Ry.0)
print Ix, Iy
Ix == Iy
```

False before and True after. Better not detect equality in some convoluted cases than claim equality for different ideals.

comment:21 in reply to: ↑ 20 Changed 10 years ago by john_perry

False before and True after. Better not detect equality in some convoluted cases than claim equality for different ideals.

I agree. This is pretty easily fixed, though; the concern stated is that the orders might differ. I'll put in a narrower test. New patch on its way...

comment:22 Changed 10 years ago by john_perry

• Status changed from needs_work to needs_review

I added your example as a test, and another for the orderings.

By the way, I'm sorry the patch is showing so many changes; I don't think there are that many, but somehow it thinks a lot of stuff was removed, then put back in. That actually did happen, but I thought I put things in the same order.

comment:23 Changed 10 years ago by novoselt

• Status changed from needs_review to needs_work

"at this point, the ideals are the same, except perhaps the term order" - you meant that rings are the same, not ideals

There are still two doctest errors according to patchbot.

comment:24 follow-up: ↓ 25 Changed 10 years ago by novoselt

Oh, and "OUTPUT:" is usually on a separate line separated by a black line from the actual description:

comment:25 in reply to: ↑ 24 Changed 10 years ago by john_perry

There are still two doctest errors according to patchbot.

I caught it too, after I uploaded the patch. New one in a moment.

Oh, and "OUTPUT:" is usually on a separate line separated by a black line from the actual description:

I was following the practice I saw elsewhere in these files (quite a few places), but I'll change it.

comment:26 Changed 10 years ago by john_perry

• Status changed from needs_work to needs_review

New patch ready. I've run doctests in sage/rings, as well the ones that had failed earlier, & those all pass. Hopefully the patchbot won't uncover any others.

comment:27 Changed 10 years ago by john_perry

All tests pass on my machine.

comment:28 follow-up: ↓ 30 Changed 10 years ago by 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).

Also, there is one thing you didn't fix: If the Gröbner basis of only one of the two to-be-compared ideals is not in the cache, then a copy of the two ideals is created using degrevlex term order, and then the Gröbner basis is computed in the supposedly easier order. However, the ring change happens even if the ideals already are in degrevlex order, and moreover the result of the Gröbner basis computation is not cached. For that problem, I had already opened #12987.

By the way, good that you do not try to change comparison of polynomial ideals into a generator-wise comparison - the ticket description let the impression arise that you want to drop Gröbner bases.

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.

Possible idea: 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. Hence, when doing a comparison and computing the Gröbner basis of a copy of ideal J in "degrevlex" order (while J lives in a ring with different order), then `J._gb_by_term_order_["degrevlex"]` should store the result.

A related topic: Avoid using comparison and hash when passing argument attributes in singular_function. See #12977 (needs review).

Another thing: This ticket's component should be "commutative algebra", not "algebra". And I guess Martin should be Cc.

comment:29 Changed 10 years ago by novoselt

• Status changed from needs_review to needs_work
• Work issues changed from documentation to cache handling

comment:30 in reply to: ↑ 28 ; follow-up: ↓ 31 Changed 10 years ago by john_perry

• Component changed from algebra to commutative algebra
• Status changed from needs_work to needs_info

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. 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?

Also, there is one thing you didn't fix: If the Gröbner basis of only one of the two to-be-compared ideals is not in the cache, then a copy of the two ideals is created using degrevlex term order, and then the Gröbner basis is computed in the supposedly easier order.

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.) That third timeit is definitely a lot slower with this patch installed.

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. A Groebner basis of an ideal could be stored in a dictionary for each different term ordering requested. As far as I can tell, this isn't possible now, and I don't know if it's feasible at all, given the reliance on Singular.

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?

Hence, when doing a comparison and computing the Gröbner basis of a copy of ideal J in "degrevlex" order (while J lives in a ring with different order), then `J._gb_by_term_order_["degrevlex"]` should store the result.

This can, of course, be done now. I will try to work on it over the next few days.

By the way, good that you do not try to change comparison of polynomial ideals into a generator-wise comparison - the ticket description let the impression arise that you want to drop Gröbner bases.

FWIW, I didn't write that part. I wrote the part where I said we would use Groebner bases. ;-)

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.

Another thing: This ticket's component should be "commutative algebra"...

I agree.

comment:31 in reply to: ↑ 30 ; follow-up: ↓ 32 Changed 10 years ago by 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.

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.

comment:32 in reply to: ↑ 31 ; follow-up: ↓ 33 Changed 10 years ago by john_perry

• Reviewers changed from Andrey Novoseltsev to Andrey Novoseltsev, Simon King

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.

comment:33 in reply to: ↑ 32 ; follow-up: ↓ 34 Changed 10 years ago by SimonKing

The only part that surprises me is that items with the same hash are put into a bucket. I had learned hashes differently.

Isn't that how hash tables work? Sorry, I am not a computer scientist, it could easily be that I misunderstood the internals of dictionaries.

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? 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.

Perhaps one could make ideals non-hashable? After all, what one needs in applications (to my experience) is the tuple of generators of the ideal.

This strikes me as a significantly different problem, albeit related, deserving of its own ticket.

OK.

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?

Sorry, have to catch a bus. I hope I don't forget to answer later. But perhaps Nicolas beats me to it?

comment:34 in reply to: ↑ 33 ; follow-up: ↓ 35 Changed 10 years ago by john_perry

Replying to 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 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,x5+x+1> and J=<x5+1,x5+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.

comment:35 in reply to: ↑ 34 ; follow-up: ↓ 36 Changed 10 years ago by SimonKing

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.

comment:36 in reply to: ↑ 35 Changed 10 years ago by john_perry

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.

I don't think so, either. I don't see any way to add or subtract generators from the ideal. Well, is there a conceivable use for the hash of an ideal? For example, would someone need a set of ideals for something? I'm pretty sure this is a possibility.

(Incidentally, when I wrote, "If so, the answer is easy," I meant, "If not, the answer is easy.")

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:

In that case, and if we can agree that someone might want to hash ideals, I suggest we using the degrevlex Groebner basis for the hash, and include a warning in the documentation that using an ideal with anything that requires a hash could slow things down seriously. That way, people have been warned. If this slows down some Sage functions that rely on dictionaries, we could rewrite them to avoid that, as you are doing with #12977.

Personally, I would rather have no hash than an incorrect one, even for immutable objects. That said, it could be a valid long-term project to find a hash for ideals.

I promised to provide you with a ticket number for multiple realisations: #7980.

Thanks. I'll look at it.

comment:37 Changed 10 years ago by john_perry

• Status changed from needs_info to needs_review

I'm about to upload a new patch that uses Simon's `_gb_by_ordering` idea. Here are the timings on the same machine as the other day:

```sage: P.<x,y> = QQ[]
<+ 30*y + 25, 1/400*x^4*y^4 - 1/5*x^5*y^2 - 1/20*x^4*y^3 + 4*x^6 + 2*x^5*y + 11/20*x^4*y^2 - 12*x^5 - 3*x^4*y + 9*x^4]*P
sage: J2 = J.gens()*P
sage: %timeit J==J2
5 loops, best of 3: 376 µs per loop
sage: _ = J.groebner_basis()
sage: %timeit J==J2
625 loops, best of 3: 372 µs per loop
sage: _ = J2.groebner_basis()
sage: %timeit J==J2
625 loops, best of 3: 362 µs per loop
```

A more than 1000-fold increase. :-)

All tests in sage/rings pass muster, as do the tests in schemes that had failed the other day.

comment:38 follow-up: ↓ 39 Changed 10 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues changed from cache handling to fix tests; is the cache pickled?

I can confirm the 1000-fold speed-up. Great!

However, the patch bot finds a few doctest errors. They are clearly related to this patch.

By the way: Could you also provide a test that confirms that '_gb_by_ordering' is preserved when copying/pickling an ideal?

comment:39 in reply to: ↑ 38 Changed 10 years ago by john_perry

However, the patch bot finds a few doctest errors. They are clearly related to this patch.

Thanks for pointing them out. They look easy.

By the way: Could you also provide a test that confirms that '_gb_by_ordering' is preserved when copying/pickling an ideal?

I should have an updated patch out by the end of the day

comment:40 Changed 10 years ago by john_perry

• Status changed from needs_work to needs_review

New file fixes the previously broken doctests, and adds a pickling test for `__gb_by_ordering`.

comment:41 follow-up: ↓ 43 Changed 10 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues changed from fix tests; is the cache pickled? to Patch commit messages

As much as I understand, both patches need proper commit messages (also containing the ticket number).

comment:42 Changed 10 years ago by novoselt

The second one definitely needs a non-queue message, but there is no need in the ticket number, it will be added automatically during merge.

comment:43 in reply to: ↑ 41 Changed 10 years ago by john_perry

• Status changed from needs_work to needs_review

As much as I understand, both patches need proper commit messages (also containing the ticket number).

Okidoki. Whether the ticket number is required or not, it's no skin off my back.

comment:44 Changed 10 years ago by SimonKing

For the patchbot:

comment:45 Changed 10 years ago by SimonKing

• Status changed from needs_review to positive_review

The tests with 5.0 ran fine, and the patchbot only finds a probably unrelated timeout with 5.1.beta. So, I'd say the patch looks fine, solves the problem, and the speed-up is impressive. Positive review.

comment:46 Changed 9 years ago by jdemeyer

• Status changed from positive_review to needs_work

What's up with all the whitespace changes in trac_12802_and_12839.patch? Please don't do this, it will only cause merge conflicts. Removing whitespace in/around code you change is fine (even encouraged), but don't just do this everywhere.

comment:47 Changed 9 years ago by novoselt

Any progress on whitespace removal? Looks like that's the only issue here!

comment:48 Changed 9 years ago by john_perry

I plan to do it, sooner rather than later. It just hasn't been as high a priority as some other things.

comment:49 Changed 9 years ago by john_perry

• Description modified (diff)
• Status changed from needs_work to needs_review

I reworked the patches into one, which lacks the changes to whitespace. Two notes:

1. I'm working with sage 5.0.1 here; I haven't downloaded 5.1 yet on any of my machines. I think this should work all the same. I'll download 5.1 next week and try it.
2. I have not yet tested all of sage. I did run tests on all the files that have been modified; these were the only ones that had problems in the past. I am running doctests now, but if anyone sees a problem before I do, please do say.

(Sorry about the whitespace thing, by the way; I got a little overeager on it.)

Last edited 9 years ago by john_perry (previous) (diff)

comment:50 Changed 9 years ago by john_perry

• Status changed from needs_review to needs_work

There's a problem with some files regarding schemes -- I think I know the cause, and will fix it soon.

comment:51 Changed 9 years ago by john_perry

• Status changed from needs_work to needs_review

Okay, a diff performed on the results of different patches showed the problems.

Most tests passed before I interrupted the previous run; I've checked that the previous failures now pass. I'm running tests now on the files that were not checked before.

comment:52 Changed 9 years ago by john_perry

All tests pass on my machine.

comment:53 Changed 9 years ago by SimonKing

In order to tell the patch bot what to do:

Apply trac_12802_no_whitespace.patch

comment:55 Changed 9 years ago by jdemeyer

• Status changed from needs_review to needs_work
• Work issues changed from Patch commit messages to Patch commit message

The new patch still needs a good commit message. This patch isn't about "no white space", it's about ideals...

Changed 9 years ago by john_perry

should incorporate other patches, without the removal of whitespace

comment:56 Changed 9 years ago by john_perry

• Status changed from needs_work to needs_review

comment:57 Changed 9 years ago by jdemeyer

• Status changed from needs_review to positive_review
• Work issues Patch commit message deleted

comment:58 follow-up: ↓ 59 Changed 9 years ago by nbruin

How much precedent do we have to let < and > mean a containment partial ordering? Doesn't the presence of '<' make that "sort" doesn't throw an error and instead produces arbitrary results?

comment:59 in reply to: ↑ 58 Changed 9 years ago by john_perry

How much precedent do we have to let < and > mean a containment partial ordering? Doesn't the presence of '<' make that "sort" doesn't throw an error and instead produces arbitrary results?

This problem predated the patch! As the original report points out, `<` returned a result before, but the result was wrong. There was already a `__cmp__` method, so the choices were either to remove it or make sure that something else trumped it. Hence the introduction of `__lt__`, etc.

As long as there is a `__cmp__`, there will be an ordering -- and Python supplies a `__cmp__` when none is given.

(Or am I wrong?)

comment:60 Changed 9 years ago by nbruin

Not all python types admit comparison

```sage: complex(1,2)<complex(1,3)
TypeError: no ordering relation is defined for complex numbers
```

but you're right that by default it seems they do:

```sage: class B(object):
....:     pass
....:
sage: b1=B()
sage: b2=B()
sage: b1 < b2
False
sage: b2 < b1
True
```

That changes with Python 3, though.

comment:61 Changed 9 years ago by john_perry

Apparently, complex is a built-in class; I can't find the source that makes it avoid comparison. However, it makes sense to raise an error in the case where the ideals are incomparable. I wouldn't raise a TypeError?, though, but a ValueError?. Does that sound acceptable? If so, I'll change the status to Needs Work (AGAIN) and upload a new patch...

comment:62 follow-up: ↓ 63 Changed 9 years ago by novoselt

What exactly does it mean "incomparable ideals"? If `I < J` means "Is I a subideal of J?", it always can be answered: if `I` leaves in a different ring without coercions - the answer is just "no". So I don't think any errors have to be thrown.

I also think that it is useful to be able to sort any mix of anything, so `sort` should never though an error, even if the result depends on the position of objects in memory.

comment:63 in reply to: ↑ 62 Changed 9 years ago by nbruin

I also think that it is useful to be able to sort any mix of anything, so `sort` should never though an error, even if the result depends on the position of objects in memory.

That just leads to silently incorrect code. If you want to sort on `id` you can do sort(L,key=id)

```sage: sorted([-10,-11,123,124,1000],key=id)
[123, -10, -11, 124, 1000]
sage: sorted([-10,-11,123,124,1000],key=id)
[124, 1000, 123, -10, -11]
sage: sorted([-10,-11,123,124,1000],key=id)
[-11, 124, 123, -10, 1000]
```

I'm curious to see a useful application of this.

This is all a bit off-topic, though. There IS precedent in python to use `<` for partial ordering.

```sage: set([2])<set([1,2,3])
True
sage: set([1,2,3])<set([3])
False
sage: set([1,2,3])<set([4,5])
False
sage: set([4,5])<set([1,2,3])
False
```

so supporting this for ideals should be fine. I'd throw an error if the ideals are "incompatible" for comparison (according to coercion rules for common covering structure, I'd say), but `False` would be consistent too (it's a partial ordering, after all).

comment:64 Changed 9 years ago by jdemeyer

• Merged in set to sage-5.4.rc0
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.