Opened 9 years ago

Closed 9 years ago

#10468 closed defect (fixed)

Cache of infinite polynomial rings is broken

Reported by: SimonKing Owned by: malb
Priority: major Milestone: sage-4.6.2
Component: commutative algebra Keywords: infinite polynomial ring cache
Cc: Merged in: sage-4.6.2.alpha1
Authors: Simon King Reviewers: Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

At #10467, I had some example of a computation of a symmetric Gröbner basis of an ideal in an infinite polynomial ring; the patch there provided quite a speedup.

However, I found that the actual reason for the original slowness is the fact that in the method tensor_with_ring, the InfinitePolynomialRing constructor is not used. Therefore, (a) the cache breaks, and (b) much time is wasted by creating the same infinite polynomial ring over and over again. Here is a new patch, independent of #10467, solving the issue.

Without the patch:

sage: R.<x,y> = InfinitePolynomialRing(QQ)
sage: R.tensor_with_ring(QQ) is R
False
sage: I = R.ideal([x[1]^2+y[2]*y[3], x[2]*y[1]*x[3]-y[1]*y[2]])
sage: %time I.groebner_basis()
CPU times: user 23.09 s, sys: 0.02 s, total: 23.11 s
Wall time: 23.67 s
[y_2*y_1^3 + y_2*y_1^2, y_2^2*y_1 - y_2*y_1^2, y_3*y_1 - y_2*y_1, x_1*y_2*y_1^2 + x_1*y_2*y_1, x_1^2 + y_2*y_1, x_2*y_2*y_1 - x_1*y_2*y_1, x_2*x_1*y_3 - y_2*y_1, x_3*y_2*y_1 - x_1*y_2*y_1, x_3*x_1*y_2 - y_2*y_1, x_3*x_2*y_1 - y_2*y_1]

With the new patch:

sage: R.<x,y> = InfinitePolynomialRing(QQ)
sage: R.<x,y> = InfinitePolynomialRing(QQ)
sage: R.tensor_with_ring(QQ) is R
True
sage: I = R.ideal([x[1]^2+y[2]*y[3], x[2]*y[1]*x[3]-y[1]*y[2]])
sage: %time I.groebner_basis()
CPU times: user 1.68 s, sys: 0.02 s, total: 1.70 s
Wall time: 2.17 s
[y_2*y_1^3 + y_2*y_1^2, y_2^2*y_1 - y_2*y_1^2, y_3*y_1 - y_2*y_1, x_1*y_2*y_1^2 + x_1*y_2*y_1, x_1^2 + y_2*y_1, x_2*y_2*y_1 - x_1*y_2*y_1, x_2*x_1*y_3 - y_2*y_1, x_3*y_2*y_1 - x_1*y_2*y_1, x_3*x_1*y_2 - y_2*y_1, x_3*x_2*y_1 - y_2*y_1]

The fix is doc tested.

Attachments (1)

10468_infinite_polynomial_ring_cache.patch (3.4 KB) - added by SimonKing 9 years ago.
Use the InfinitePolynomialRing? constructor in the tensor_with_ring methods

Download all attachments as: .zip

Change History (9)

Changed 9 years ago by SimonKing

Use the InfinitePolynomialRing? constructor in the tensor_with_ring methods

comment:1 Changed 9 years ago by SimonKing

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by mhansen

  • Status changed from needs_review to positive_review

Looks good to me.

comment:3 Changed 9 years ago by jdemeyer

Please set milestone.

comment:4 Changed 9 years ago by SimonKing

  • Milestone set to sage-4.6.1

Since it has a positive review, I choose the next possible milestone.

comment:5 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:6 Changed 9 years ago by davidloeffler

  • Reviewers set to Mike Hansen

comment:7 Changed 9 years ago by SimonKing

Will the patch be merged, after meanwhile 5 weeks?

comment:8 Changed 9 years ago by jdemeyer

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