#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 john_perry):
* status: needs_work => needs_info
* component: algebra => commutative algebra
Comment:
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. 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.
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?
> 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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12802#comment:30>
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.
