Opened 12 years ago

Closed 12 years ago

# Slowness of InfinitePolynomialRing basic arithmetic

Reported by: Owned by: SimonKing SimonKing major sage-4.3 commutative algebra infinite polynomial ring, basic arithmetic sage-4.3.alpha1 Simon King Martin Albrecht N/A

### Description

Martin Albrecht reported the following example:

```sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x10000 = x
sage: x10001 = x
sage: %time 1/2*x10000
CPU times: user 43.09 s, sys: 0.02 s, total: 43.12 s
Wall time: 43.12 s
1/2*x10000
```

This is inacceptably slow.

Note that this problem does not occur with the sparse implementation of infinite polynomial rings:

```sage: X.<x> = InfinitePolynomialRing(QQ,implementation='sparse')
sage: x10000 = x
sage: x10001 = x
sage: %time 1/2*x10000
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
1/2*x10000
```

Part of the problem is a slowness of element conversion in polynomial rings:

```sage: R1 = PolynomialRing(QQ,'x',10001)
sage: R2 = PolynomialRing(QQ,'x',10002)
sage: x10000 = R1('x10000')
sage: %time a = R2(x10000)
CPU times: user 4.96 s, sys: 0.12 s, total: 5.08 s
Wall time: 5.11 s
```

which is rather slow as well.

### Changed 12 years ago by SimonKing

Improving basic arithmetic of infinite polynomial rings

### comment:1 Changed 12 years ago by SimonKing

• Status changed from new to needs_review

With the attached patch, the example improves a lot:

```sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x10000 = x
sage: x10001 = x
sage: %time 1/2*x10000
CPU times: user 7.37 s, sys: 0.01 s, total: 7.38 s
Wall time: 7.38 s
1/2*x10000
```

Of course, this is still a shame. But it may be better than nothing.

The idea / reason for the slowness:

• When x10001 is created, the underlying finite polynomial ring of X changes. At this point, the underlying finite polynomial of x10000 does not belong to the underlying ring of X anymore.
• In the old code, the underlying finite polynomial of x10000 was not updated.
• With the patch, it will be updated as soon as x10000 is involved in any multiplication, summation or difference.

Hence, the timing is essentially reduced to the time for conversion of the underlying polynomials; namely, after restarting sage (clearing the cache):

```sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x10000 = x
sage: x10001 = x
sage: %time x10000._p = X._P(x10000._p)
CPU times: user 6.90 s, sys: 0.01 s, total: 6.91 s
Wall time: 6.91 s
```

I don't think that this is a satisfying time, but it is some progress, and as long as element conversion for polynomial rings isn't improved, I see no way to do it better.

### comment:2 Changed 12 years ago by malb

• Status changed from needs_review to positive_review

The change seems sensible, applies cleanly against 4.3.alpha0, doctests pass. positive review.

### comment:3 Changed 12 years ago by mhansen

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