Sage: Ticket #7578: Slowness of InfinitePolynomialRing basic arithmetic
https://trac.sagemath.org/ticket/7578
<p>
<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/20e0fc8f5c5be582"><span class="icon"></span>Martin Albrecht</a> reported the following example:
</p>
<pre class="wiki">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
</pre><p>
This is inacceptably slow.
</p>
<p>
Note that this problem does not occur with the sparse implementation of infinite polynomial rings:
</p>
<pre class="wiki">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
</pre><p>
Part of the problem is a slowness of element conversion in polynomial rings:
</p>
<pre class="wiki">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
</pre><p>
which is rather slow as well.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7578
Trac 1.1.6SimonKingTue, 01 Dec 2009 23:22:09 GMTattachment set
https://trac.sagemath.org/ticket/7578
https://trac.sagemath.org/ticket/7578
<ul>
<li><strong>attachment</strong>
set to <em>7578_basic_arithmetic.patch</em>
</li>
</ul>
<p>
Improving basic arithmetic of infinite polynomial rings
</p>
TicketSimonKingTue, 01 Dec 2009 23:50:45 GMTstatus changed
https://trac.sagemath.org/ticket/7578#comment:1
https://trac.sagemath.org/ticket/7578#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
With the attached patch, the example improves a lot:
</p>
<pre class="wiki">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
</pre><p>
Of course, this is still a shame. But it may be better than nothing.
</p>
<p>
The idea / reason for the slowness:
</p>
<ul><li>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.
</li><li>In the old code, the underlying finite polynomial of x10000 was not updated.
</li><li>With the patch, it will be updated as soon as x10000 is involved in any multiplication, summation or difference.
</li></ul><p>
Hence, the timing is essentially reduced to the time for conversion of the underlying polynomials; namely, after restarting sage (clearing the cache):
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
TicketmalbWed, 02 Dec 2009 11:36:44 GMTstatus changed
https://trac.sagemath.org/ticket/7578#comment:2
https://trac.sagemath.org/ticket/7578#comment:2
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
The change seems sensible, applies cleanly against 4.3.alpha0, doctests pass. positive review.
</p>
TicketmhansenWed, 02 Dec 2009 12:39:08 GMTstatus changed; reviewer, resolution, merged set
https://trac.sagemath.org/ticket/7578#comment:3
https://trac.sagemath.org/ticket/7578#comment:3
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Martin Albrecht</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.3.alpha1</em>
</li>
</ul>
Ticket