Opened 9 years ago

Closed 9 years ago

Cache of infinite polynomial rings is broken

Reported by: Owned by: SimonKing malb major sage-4.6.2 commutative algebra infinite polynomial ring cache sage-4.6.2.alpha1 Simon King Mike Hansen N/A

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^2+y*y, x*y*x-y*y])
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^2+y*y, x*y*x-y*y])
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.

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