Opened 11 years ago

Closed 11 years ago

#7578 closed defect (fixed)

Slowness of InfinitePolynomialRing basic arithmetic

Reported by: SimonKing Owned by: SimonKing
Priority: major Milestone: sage-4.3
Component: commutative algebra Keywords: infinite polynomial ring, basic arithmetic
Cc: Merged in: sage-4.3.alpha1
Authors: Simon King Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

Martin Albrecht reported the following example:

sage: X.<x> = InfinitePolynomialRing(QQ)
sage: x10000 = x[10000]
sage: x10001 = x[10001]
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[10000]
sage: x10001 = x[10001]
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.

Attachments (1)

7578_basic_arithmetic.patch (1.3 KB) - added by SimonKing 11 years ago.
Improving basic arithmetic of infinite polynomial rings

Download all attachments as: .zip

Change History (4)

Changed 11 years ago by SimonKing

Improving basic arithmetic of infinite polynomial rings

comment:1 Changed 11 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[10000]
sage: x10001 = x[10001]
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[10000]
sage: x10001 = x[10001]
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 11 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 11 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.