Opened 12 years ago

Closed 12 years ago

Cache of infinite polynomial rings is broken

Reported by: Owned by: Simon King Martin Albrecht 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[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.

Changed 12 years ago by Simon King

Use the InfinitePolynomialRing? constructor in the tensor_with_ring methods

comment:1 Changed 12 years ago by Simon King

Status: new → needs_review

comment:2 Changed 12 years ago by Mike Hansen

Status: needs_review → positive_review

Looks good to me.

comment:4 Changed 12 years ago by Simon King

Milestone: → sage-4.6.1

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

comment:5 Changed 12 years ago by Jeroen Demeyer

Milestone: sage-4.6.1 → sage-4.6.2

comment:6 Changed 12 years ago by David Loeffler

Reviewers: → Mike Hansen

comment:7 Changed 12 years ago by Simon King

Will the patch be merged, after meanwhile 5 weeks?

comment:8 Changed 12 years ago by Jeroen Demeyer

Merged in: → sage-4.6.2.alpha1 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.