Opened 8 years ago

Closed 7 years ago

#12987 closed defect (duplicate)

When comparing ideals, try to avoid computing the Gröbner basis of a copy of the ideal

Reported by: SimonKing Owned by: malb
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: commutative algebra Keywords:
Cc: malb Merged in:
Authors: Reviewers: Simon King
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12802 Stopgaps:

Description

We define a polynomial ring, some ideal, and a copy of that ideal.

sage: P.<x,y> = QQ[]
sage: J = [x^4*y^4 + 2*x^2*y^5 + y^6 - 2/3*x^2*y^2 - 2/3*y^3 + 1/9, 9/16*y^6 - x^2*y^3 + 3/2*x*y^4 + 1/2*y^5 + 4/9*x^4 - 4/3*x^3*y + 5/9*x^2*y^2 + 2/3*x*y^3 + 1/9*y^4 + 12*y^3 - 32/3*x^2 + 16*x*y + 16/3*y^2 + 64, y^8 - 2/5*x^3*y^4 + 1/25*x^6 - 4/11*x*y^4 + 6*y^5 + 4/55*x^4 - 6/5*x^3*y + 10*y^4 - 2*x^3 + 4/121*x^2 - 12/11*x*y + 9*y^2 - 20/11*x + 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

We have:

sage: %timeit J==J2
5 loops, best of 3: 642 ms per loop
sage: _ = J.groebner_basis()
sage: %timeit J==J2
5 loops, best of 3: 642 ms per loop
sage: _ = J2.groebner_basis()
sage: %timeit J==J2
625 loops, best of 3: 6.67 µs per loop

Hence, only when the Gröbner bases of both arguments are cached, then the cached Gröbner bases are used. As one can see by reading the code, even if only one argument does not have the Gröbner basis cached, then Gröbner bases are computed for degrevlex copies of both arguments.

Why copies? We have the same ring here, and we have degrevlex anyway. So, there is no need to copy.

Suggestion: Make the algorithm slightly more clever, so that taking a copy is avoided when the ring is degrevlex anyway. One could also consider to prepend a quick test, such as: Compare the set of generators, and compute Gröbner bases only if the quick test does not suffice to prove equality.

Change History (5)

comment:1 Changed 8 years ago by SimonKing

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by SimonKing

  • Milestone changed from sage-5.1 to sage-duplicate/invalid/wontfix
  • Reviewers set to Simon King
  • Status changed from needs_review to positive_review

It seems that this problem shall be dealt with at #12802. Hence, I'll mark it as duplicate.

comment:3 Changed 8 years ago by jdemeyer

  • Dependencies set to #12802

comment:4 Changed 8 years ago by SimonKing

Jeroen, why "dependency"? This here is really just a duplicate.

comment:5 Changed 7 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
  • Summary changed from When comparing ideals, ty to avoid computing the Gröbner basis of a copy of the ideal to When comparing ideals, try to avoid computing the Gröbner basis of a copy of the ideal
Note: See TracTickets for help on using tickets.