Sage: Ticket #9944: categories for polynomial rings
https://trac.sagemath.org/ticket/9944
<p>
Currently, they're always just commutative rings.
</p>
<p>
<strong>Apply:</strong>
</p>
<ol><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/9944-poly-cat.patch" title="Attachment '9944-poly-cat.patch' in Ticket #9944">9944-poly-cat.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/9944-poly-cat.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac-9944-poly_cat_doctests.patch" title="Attachment 'trac-9944-poly_cat_doctests.patch' in Ticket #9944">trac-9944-poly_cat_doctests.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac-9944-poly_cat_doctests.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac-9944-poly-cat-review.patch" title="Attachment 'trac-9944-poly-cat-review.patch' in Ticket #9944">trac-9944-poly-cat-review.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac-9944-poly-cat-review.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Attachment 'trac9944_polynomial_speedup.patch' in Ticket #9944">trac9944_polynomial_speedup.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_abvar_endomorphism.patch" title="Attachment 'trac9944_abvar_endomorphism.patch' in Ticket #9944">trac9944_abvar_endomorphism.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_abvar_endomorphism.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_faster_and_cleaner_coercion.patch" title="Attachment 'trac9944_faster_and_cleaner_coercion.patch' in Ticket #9944">trac9944_faster_and_cleaner_coercion.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_faster_and_cleaner_coercion.patch" title="Download"></a>
</li></ol>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/9944
Trac 1.1.6robertwbSat, 18 Sep 2010 22:41:47 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>9944-poly-cat.patch</em>
</li>
</ul>
TicketrobertwbSat, 18 Sep 2010 22:41:54 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:1
https://trac.sagemath.org/ticket/9944#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketnthierySun, 19 Sep 2010 21:00:26 GMT
https://trac.sagemath.org/ticket/9944#comment:2
https://trac.sagemath.org/ticket/9944#comment:2
<blockquote>
<p>
Hi Robert!
</p>
</blockquote>
<p>
I have been through the patch, and it sounds good! I won't have the time to actually test it before some time, so please anyone beat me to it!
</p>
<p>
Just one micro question: does <a class="missing wiki">PolynomialRing?</a> actually check that the ring is commutative?
</p>
<p>
Cheers
</p>
TicketmhansenMon, 20 Sep 2010 05:19:59 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac_9944.patch</em>
</li>
</ul>
TicketmhansenMon, 20 Sep 2010 05:22:42 GMTreviewer, author set
https://trac.sagemath.org/ticket/9944#comment:3
https://trac.sagemath.org/ticket/9944#comment:3
<ul>
<li><strong>reviewer</strong>
set to <em>Nicolas M. Thiéry, Mike Hansen</em>
</li>
<li><strong>author</strong>
set to <em>Robert Bradshaw</em>
</li>
</ul>
<p>
I went ahead and moved the functionality to it's own category since we want the mathematical information at the category level. Could someone look over these changes?
</p>
TicketrobertwbMon, 20 Sep 2010 22:03:18 GMT
https://trac.sagemath.org/ticket/9944#comment:4
https://trac.sagemath.org/ticket/9944#comment:4
<p>
The first patch only concerned univarite polynomial rings, the logic is not all correct for multivariate polynomial rings (though on an orthogonal note, that could use some fixing up as well). It seems odd to have a category of univariate polynomial rings over a fixed basering, which is why I put the logic into the concrete object. I suppose the category should a be declared as a graded R-algebra as well (do we have join categories yet?).
</p>
<p>
I don't know if <a class="missing wiki">PolynomialRing?</a> asserts its basering is commutative, but IIRC it's been assumed for a long time.
</p>
TicketrobertwbFri, 03 Dec 2010 19:41:36 GMT
https://trac.sagemath.org/ticket/9944#comment:5
https://trac.sagemath.org/ticket/9944#comment:5
<p>
Apply only 9944-poly-cat.patch
</p>
TicketrobertwbWed, 26 Jan 2011 06:26:13 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>9944-poly-cat-doctests.patch</em>
</li>
</ul>
TicketrobertwbWed, 26 Jan 2011 06:27:28 GMT
https://trac.sagemath.org/ticket/9944#comment:6
https://trac.sagemath.org/ticket/9944#comment:6
<p>
Apply 9944-poly-cat.patch and 9944-poly-cat-doctests.patch .
</p>
TicketmraumWed, 23 Mar 2011 19:18:00 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac-9944-poly-cat-review.patch</em>
</li>
</ul>
TicketmraumWed, 23 Mar 2011 19:21:32 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:7
https://trac.sagemath.org/ticket/9944#comment:7
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=7">diff</a>)
</li>
</ul>
<p>
I would give this a positive review for Robert's idea and I would open a new ticket for the multivariate rings. I'll just send a mail to Mike whether he is ok with that or no.
</p>
TicketnthieryTue, 29 Mar 2011 09:23:31 GMT
https://trac.sagemath.org/ticket/9944#comment:8
https://trac.sagemath.org/ticket/9944#comment:8
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:4" title="Comment 4">robertwb</a>:
</p>
<blockquote class="citation">
<p>
The first patch only concerned univarite polynomial rings, the logic is not all correct for multivariate polynomial rings (though on an orthogonal note, that could use some fixing up as well). It seems odd to have a category of univariate polynomial rings over a fixed basering, which is why I put the logic into the concrete object. I suppose the category should a be declared as a graded R-algebra as well (do we have join categories yet?).
</p>
</blockquote>
<p>
Sorry for the very late answer. In MuPAD, we had a category for
univariate polynomial rings: there are several possible
implementations of such, and it's natural to factor out the generic
code, together with the category inheritance logic, in a category.
</p>
<p>
And yes, we have join categories. See Category.join.
</p>
<p>
I let you see whether to create the <a class="missing wiki">UnivariatePolynomialRing?</a> category
in this ticket or in a later ticket.
</p>
TicketSimonKingTue, 29 Mar 2011 15:47:34 GMT
https://trac.sagemath.org/ticket/9944#comment:9
https://trac.sagemath.org/ticket/9944#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:8" title="Comment 8">nthiery</a>:
</p>
<blockquote class="citation">
<p>
Sorry for the very late answer. In MuPAD, we had a category for
univariate polynomial rings: there are several possible
implementations of such, and it's natural to factor out the generic
code, together with the category inheritance logic, in a category.
</p>
</blockquote>
<p>
Aparently there is a doctest failure. I fixed it, but unfortunately it went into my patch submitted for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>. Therefore, "needs work".
</p>
<p>
Question: Do we really want a category of polynomial rings? Or do we want that (1) polynomial rings use the category framework (that's the purpose of my patch for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>) and (2) the category to which a given polynomial ring belongs is a bit narrower than simply "category of rings"? I hope it is the latter.
</p>
<p>
My suggestion is that I submit a small patch fixing the doctests. Please tell whether my patch for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a> improves the multivariate case. Then, perhaps it would be possible to give Roberts patches (+ doctest fix) a positive review, so that we can focus on <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>.
</p>
TicketSimonKingTue, 29 Mar 2011 16:31:53 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/9944#comment:10
https://trac.sagemath.org/ticket/9944#comment:10
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Fix one test</em>
</li>
</ul>
TicketSimonKingTue, 29 Mar 2011 17:07:08 GMT
https://trac.sagemath.org/ticket/9944#comment:11
https://trac.sagemath.org/ticket/9944#comment:11
<p>
At <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, Jason Bandlow reported a slow-down, that is at least partially caused by the patches here. Do you have any idea what could be the reason?
</p>
TicketSimonKingWed, 30 Mar 2011 06:23:00 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:12
https://trac.sagemath.org/ticket/9944#comment:12
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=12">diff</a>)
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:9" title="Comment 9">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Aparently there is a doctest failure. I fixed it, but unfortunately it went into my patch submitted for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>. Therefore, "needs work".
</p>
</blockquote>
<p>
Strange: Although the patch bot did see that error in one run, I can not reproduce it (but I had to change that test in my patch for <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>, because it turns <code>QQ['x'].category()</code> into the join of the category of euclidean domains and commutative algebras over <code>QQ</code>.
</p>
<p>
The other issue, namely the performance loss, was studied on <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/e4af3f1705b76955"><span class="icon"></span>sage-devel</a>.
</p>
<p>
Florent Hivert found that a long mro does not matter for Python, but it <em>does</em> matter if the classes inherit from a cdef class. That is the case for most classes in Sage (inheriting from <code>SageObject</code>), so, we should address the problem of a long mro.
</p>
<p>
Eventually, that should be fixed in Cython (and I think Florent reported it upstream). But for now, it seems to me we should think of a work-around.
</p>
<p>
Would it be acceptable coding practice to explicitly state in a derived class (say, <code>MPolynomialRing_generic</code>), that frequently used methods such as base or base_ring are the same as <code>Parent.base</code> or <code>Parent.base_ring</code>? David Roe stated that it might be dangerous to do so, at least if <code>cpdef</code> methods are involved.
</p>
TicketSimonKingWed, 30 Mar 2011 09:53:50 GMT
https://trac.sagemath.org/ticket/9944#comment:13
https://trac.sagemath.org/ticket/9944#comment:13
<p>
Concerning performance loss:
</p>
<p>
It seems to me that part of the reason is the fact that with the patchse, <code>__init_extra__</code> is not executed when it should. Sometimes, the parent methods of a category provide a useful <code>__init_extra__</code>, for example the category of algebras.
</p>
<p>
I am not sure yet why that happens, but I think it would happen if <code>Parent.__init__</code> is called without providing the category: Namely, doing <code>self._init_category_(...)</code> alone will <em>not</em> trigger the execution of <code>__init_extra__</code>.
</p>
TicketSimonKingWed, 30 Mar 2011 10:01:40 GMT
https://trac.sagemath.org/ticket/9944#comment:14
https://trac.sagemath.org/ticket/9944#comment:14
<p>
It seems I was right!
</p>
<p>
Namely, the whole ring stuff is (unfortunately) inherited from <code>ParentWithGens</code>, which inherits from <code>ParentWithBase</code>, which inherits from <code>parent_old.Parent</code>.
</p>
<p>
And <code>parent_old.Parent</code> inherits from "the one and only Parent" -- but forgets to call <code>Parent.__init__</code>!! Instead, it just does <code>self._init_category_(...)</code>.
</p>
<p>
I'll change it and see what happens.
</p>
TicketSimonKingWed, 30 Mar 2011 10:17:01 GMT
https://trac.sagemath.org/ticket/9944#comment:15
https://trac.sagemath.org/ticket/9944#comment:15
<p>
Very bad things happen. As soon as <code>parent.Parent.__init__</code> is called in <code>parent_old.Parent.__init__</code>, an infinite recursion occurs.
</p>
TicketSimonKingWed, 30 Mar 2011 11:25:25 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_second_referee.patch</em>
</li>
</ul>
<p>
Call Parent.<span class="underline">init</span> during initialisation of a ring
</p>
TicketSimonKingWed, 30 Mar 2011 11:31:40 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:16
https://trac.sagemath.org/ticket/9944#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=16">diff</a>)
</li>
</ul>
<p>
I attached a small patch to solve part of the problem of the missing parent initialisation: I call <code>Parent.__init__</code> and <code>ParentWithGens.__init__</code> explicitly, during initialisation of a ring. In that way, the <code>__init_extra__</code> methods are correctly picked up.
</p>
<p>
However, that does not solve the performance problem.
</p>
<p>
Question one: How can one come to speed?
</p>
<p>
Question two: Is my patch really trivial enough to be called a referee patch?
</p>
<p>
For the patchbot:
</p>
<p>
Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_second_referee.patch
</p>
TicketSimonKingWed, 30 Mar 2011 13:10:18 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/9944#comment:17
https://trac.sagemath.org/ticket/9944#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
<li><strong>work_issues</strong>
<em>Fix one test</em> deleted
</li>
</ul>
<p>
FWIW: The doc tests pass.
</p>
<p>
Here is another idea what the slow down may come from. It was pointed out by Nicolas that the mro from the polynomial ring to <code>Parent</code> does not become longer by initialising the category properly: The inheritance from category parent classes comes <em>after</em> Python inheritance. However, when all the parent classes of all super categories must be searched, it takes considerably longer before an <code>AttributeError</code> can be raised.
</p>
<p>
A similar issue has been studied at <a class="closed ticket" href="https://trac.sagemath.org/ticket/10467" title="enhancement: Improve lookup of private attributes (closed: fixed)">#10467</a>. It seems to be important that an attribute error is raised as quickly as possible. That becomes difficult, if 60 parent classes need to be searched, before one eventually finds that the requested attribute does not exist.
</p>
<p>
But probably that question is out of the scope of this ticket.
</p>
<p>
So, what shall one do? Give it a positive review and accept the deceleration, or wait until someone has a model for improved attribute access?
</p>
TicketSimonKingWed, 30 Mar 2011 13:22:22 GMT
https://trac.sagemath.org/ticket/9944#comment:18
https://trac.sagemath.org/ticket/9944#comment:18
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:17" title="Comment 17">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
A similar issue has been studied at <a class="closed ticket" href="https://trac.sagemath.org/ticket/10467" title="enhancement: Improve lookup of private attributes (closed: fixed)">#10467</a>. It seems to be important that an attribute error is raised as quickly as possible. That becomes difficult, if 60 parent classes need to be searched, before one eventually finds that the requested attribute does not exist.
</p>
</blockquote>
<p>
No, that is not the problem here! I was inserting print statements into <code>getattr_from_other_class</code> in order to find out what attributes are actually requested from the category when doing arithmetic. It turned out that, during the first computation of <code>(2*x-1)^2+5</code>, some attributes are requested. But when one repeats that computation, <code>getattr_from_other_class</code> is <em>not</em> involved.
</p>
<p>
But what else could be the reason?
</p>
TicketSimonKingWed, 30 Mar 2011 19:12:21 GMT
https://trac.sagemath.org/ticket/9944#comment:19
https://trac.sagemath.org/ticket/9944#comment:19
<p>
Perhaps it is a conversion map that is slower than necessary?
</p>
<p>
If you look at <code>sage.categories.algebras.Algebras.ParentMethods.__init_extra__</code>, you see that it tries to register a certain set morphism as a coercion from the base ring into the algebra (that obviously works only if the algebra is unital).
</p>
<p>
But aparently a different coercion is used -- a slower coercion!
</p>
<p>
Namely, together with my patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: R.category() # the __init_extra__ was supposed to be used.
Join of Category of unique factorization domains and Category of commutative algebras over Integer Ring
sage: c = R.convert_map_from(R.base_ring())
sage: c
Polynomial base injection morphism:
From: Integer Ring
To: Univariate Polynomial Ring in x over Integer Ring
</pre><p>
That is not what <code>__init_extra__</code> attempted to register!
</p>
<p>
Let us compare:
</p>
<pre class="wiki">sage: from sage.categories.morphism import SetMorphism
sage: H = R.base().Hom(R)
sage: f = SetMorphism(H,R.from_base_ring)
sage: timeit('c(100)',number=10^5)
100000 loops, best of 3: 8.13 Âµs per loop
sage: timeit('f(100)',number=10^5)
100000 loops, best of 3: 1.75 Âµs per loop
</pre><p>
So, things could be considerably improved. Obvious questions: Will <code>from_base</code> always yield a faster approach than the base injection morphism? And can we enforce to use the faster coercion?
</p>
<p>
Aparently it is not so easy:
</p>
<pre class="wiki">sage: AC = Algebras(ZZ).parent_class
sage: R._unset_coercions_used()
sage: AC.__init_extra__(R)
sage: R.convert_map_from(R.base_ring())
Polynomial base injection morphism:
From: Integer Ring
To: Univariate Polynomial Ring in x over Integer Ring
sage: R._unset_coercions_used()
sage: f.register_as_coercion()
sage: R.convert_map_from(R.base_ring())
Polynomial base injection morphism:
From: Integer Ring
To: Univariate Polynomial Ring in x over Integer Ring
</pre><p>
Can you explain how to force the use of a particular map for coercion of the base ring?
</p>
TicketSimonKingWed, 30 Mar 2011 19:28:03 GMT
https://trac.sagemath.org/ticket/9944#comment:20
https://trac.sagemath.org/ticket/9944#comment:20
<p>
And aparently the univariate polynomial rings are special in their choice of a conversion from the base ring. Again with <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>
</p>
<pre class="wiki">sage: R.<m> = ZZ[]
sage: R.convert_map_from(R.base_ring())
Polynomial base injection morphism:
From: Integer Ring
To: Univariate Polynomial Ring in m over Integer Ring
sage: R.<x,y> = QQ['t'][]
sage: R.convert_map_from(R.base_ring())
Generic morphism:
From: Univariate Polynomial Ring in t over Rational Field
To: Multivariate Polynomial Ring in x, y over Univariate Polynomial Ring in t over Rational Field
</pre>
TicketSimonKingThu, 31 Mar 2011 05:45:41 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/9944#comment:21
https://trac.sagemath.org/ticket/9944#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>Speedup</em>
</li>
</ul>
<p>
I suggest to speed things up by modifying "Polynomial base injection morphism". Internally, it uses rather slow ways of creating a polynomial of degree zero. It is likely to be faster to do what <code>R.from_base</code> does: Take the One of the ring (if it exists!) and use its <code>_lmul_</code> method (if it has <code>_lmul_</code>).
</p>
<p>
I also understand why <code>Algebras(...).parent_class.__init_extra__(R)</code> has no effect on the choice of a conversion map from <code>R.base()</code> to <code>R</code>: It calls <code>R.one()</code> in order to create a better coercion map; but <code>R.one()</code> will, internally, construct a conversion from the base to <code>R</code>. At that point, the "better" coercion is not defined, and thus the usual conversion is created and cached.
</p>
<p>
In other words, <code>R.from_base</code> will only be used for conversion if <code>R</code> does <em>not</em> obey the rules of the new coercion framework (e.g., if it has a custom <code>__call__</code>).
</p>
<p>
Since the polynomial base injection morphism is a specialised method, it should be possible to internally construct the One of R without invoking coercion. My plan is to combine it with <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_second_referee.patch" title="Attachment 'trac9944_second_referee.patch' in Ticket #9944">trac9944_second_referee.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_second_referee.patch" title="Download"></a> and submit a patch that then certainly needs a reviewer.
</p>
TicketSimonKingThu, 31 Mar 2011 11:15:01 GMTstatus, description, author changed
https://trac.sagemath.org/ticket/9944#comment:22
https://trac.sagemath.org/ticket/9944#comment:22
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=22">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Robert Bradshaw</em> to <em>Robert Bradshaw, Simon King</em>
</li>
</ul>
<p>
Good news! Things are now <em>faster</em> than without the patches!
</p>
<p>
I found that one can considerably improve the conversion of an element of the base ring into a polynomial ring. Some polynomial rings used a generic conversion map, some used a polynomial base injection map -- and both were slow.
</p>
<p>
My inspiration came from <code>Algebras.ParentMethods.__init_extra__</code>: If R is a polynomial ring, then multiplication of a scalar with <code>R.one()</code> often is a very fast method to convert the scalar into R.
</p>
<p>
Problems:
</p>
<ul><li>We should not assume that any ring has a unit (ok, polynomial rings over a unital ring have...).
</li><li>Calling <code>R.one()</code> will usually trigger the creation of a generic conversion - hence, it would be difficult to register it as conversion.
</li><li>Not all flavours of polynomial elements have a <code>_rmul_</code> (polynomial_element_generic has not).
</li><li>Sometimes, other conversion maps are registered when one wants to register the polynomial base injection map.
</li></ul><p>
So, I implemented <code>_rmul_</code> and <code>_lmul_</code> for polynomial_element_generic, try various ways (old and new coercion model) of creating a One bypassing conversion maps, and in one init method of polynomial rings I decided to re-initialise the conversion maps.
</p>
<p>
<strong><span class="underline">Timings</span></strong>
</p>
<p>
I tried to test as many cases (multi- versus univariate, <code>libSingular</code> and others, different base rings,...). Without all the patches, we have the following:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 23.4 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 24.6 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 87.9 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 113 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 13 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 16.6 µs per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 10.8 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 238 µs per loop
sage: R.<x,y> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 511 µs per loop
sage: R.<x> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 1.06 ms per loop
</pre><p>
With the patches, I get
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.97 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.3 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 70.3 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 82.6 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 12.6 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 16.4 µs per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 10.5 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 187 µs per loop
sage: R.<x,y> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 503 µs per loop
sage: R.<x> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 1.08 ms per loop
</pre><p>
So, there is no significant slow down at all, but a considerable speed up in most cases.
</p>
<p>
I suppose it can now be reviewed. I understood that the Robert's patches essentially have a positive review, except for the slow-down. So, would it suffice if some of you test my patch?
</p>
<p>
Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_polynomial_speedup.patch
</p>
TicketmraumThu, 31 Mar 2011 11:43:44 GMT
https://trac.sagemath.org/ticket/9944#comment:23
https://trac.sagemath.org/ticket/9944#comment:23
<p>
Wow, that is an amazingly good result! I will take my time to review this by next week. But if anybody is faster than me, feel free to go for it!
</p>
TicketnthieryThu, 31 Mar 2011 17:48:58 GMTcc set; work_issues deleted
https://trac.sagemath.org/ticket/9944#comment:24
https://trac.sagemath.org/ticket/9944#comment:24
<ul>
<li><strong>cc</strong>
<em>sage-combinat</em> added
</li>
<li><strong>work_issues</strong>
<em>Speedup</em> deleted
</li>
</ul>
<p>
That's excellent indeed! Thanks!
</p>
<p>
Simon: I guess I'll focus on the reviewing of the other patches.
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketnthieryThu, 31 Mar 2011 17:58:52 GMT
https://trac.sagemath.org/ticket/9944#comment:25
https://trac.sagemath.org/ticket/9944#comment:25
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:22" title="Comment 22">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Problems:
</p>
<ul><li>We should not assume that any ring has a unit (ok, polynomial rings over a unital ring have...).
</li></ul></blockquote>
<p>
Rings() assumes its objects to be unital. If we want to support
polynomials over non unital rings, then this should go through the use
of Rngs(). If we make sure the coercion morphism from the base ring is always declared by Algebras(), all we will have to do is to use some new category <a class="missing wiki">NonUnitalAlgebras?</a>() when the base ring is just in Rngs(). Bwt: having a <a class="missing wiki">PolynomialRings?</a>() (<a class="missing wiki">PolynomialRngs?</a>?) category would be a good way to factor out this logic.
</p>
<p>
But one thing at a time :-)
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TicketmraumFri, 01 Apr 2011 00:33:33 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac-9944-poly_cat_doctests.patch</em>
</li>
</ul>
TicketmraumFri, 01 Apr 2011 00:38:58 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:26
https://trac.sagemath.org/ticket/9944#comment:26
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=26">diff</a>)
</li>
</ul>
<p>
I applied the second patch and exported the commit, so that Jeroen will have an easier life (<a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/f5a9c012f6299a9e"><span class="icon"></span>http://groups.google.com/group/sage-devel/browse_thread/thread/f5a9c012f6299a9e</a>).
</p>
<p>
The patchs are very good. I am waiting for the tests to finish, but I guess this will be through very soon.
</p>
TicketmraumFri, 01 Apr 2011 00:53:06 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/9944#comment:27
https://trac.sagemath.org/ticket/9944#comment:27
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Nicolas M. Thiéry, Mike Hansen</em> to <em>Nicolas M. Thiéry, Mike Hansen, Martin Raum</em>
</li>
</ul>
<p>
The speed up is significant and all tests pass. This gets a positive review.
</p>
<p>
Let me point out the following (that won't show up in many use case, but still might deserve some consideration later):
</p>
<p>
unpatched:
</p>
<pre class="wiki">sage: R = PolynomialRing(ZZ, ['a' + str(n) for n in range(10000)])
sage: x = R.gen(0)
sage: timeit('(2*x - 1)^2 + 5', number = 10^4)
10000 loops, best of 3: 94.5 µs per loop
</pre><p>
patched:
</p>
<pre class="wiki">sage: R = PolynomialRing(ZZ, ['a' + str(n) for n in range(10000)])
sage: x = R.gen(0)
sage: timeit('(2*x - 1)^2 + 5', number = 10^4)
10000 loops, best of 3: 131 µs per loop
</pre>
TicketjdemeyerTue, 12 Apr 2011 11:51:09 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:28
https://trac.sagemath.org/ticket/9944#comment:28
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
The PDF documentation doesn't build:
</p>
<pre class="wiki">! Missing { inserted.
<to be read again>
$
l.358009 ...ment with the One by means of $_rmul_$
.
?
! Emergency stop.
<to be read again>
$
l.358009 ...ment with the One by means of $_rmul_$
.
! ==> Fatal error occurred, no output PDF file produced!
Transcript written on reference.log.
make[1]: *** [reference.pdf] Error 1
</pre>
TicketSimonKingWed, 13 Apr 2011 12:44:19 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:29
https://trac.sagemath.org/ticket/9944#comment:29
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
It should now be fine. The problem was single back tick (Latex math mode) versus double back tick (verbose code).
</p>
TicketSimonKingWed, 13 Apr 2011 13:59:59 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:30
https://trac.sagemath.org/ticket/9944#comment:30
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
Sorry, I changed but one instance of single back tick versus double back tick. But there are more left. So, needs work, for now.
</p>
TicketSimonKingWed, 13 Apr 2011 14:12:55 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_polynomial_speedup.patch</em>
</li>
</ul>
<p>
Speedup of polynomial arithmetic by improved base ring conversion
</p>
TicketSimonKingWed, 13 Apr 2011 14:14:03 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:31
https://trac.sagemath.org/ticket/9944#comment:31
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Now it seems solved. <code>sage -docbuild all html</code> did not complain!
</p>
<p>
Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_polynomial_speedup.patch
</p>
TicketjdemeyerWed, 13 Apr 2011 15:35:11 GMTmilestone changed
https://trac.sagemath.org/ticket/9944#comment:32
https://trac.sagemath.org/ticket/9944#comment:32
<ul>
<li><strong>milestone</strong>
changed from <em>sage-4.7</em> to <em>sage-4.7.1</em>
</li>
</ul>
TicketjdemeyerWed, 13 Apr 2011 19:45:23 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/9944#comment:33
https://trac.sagemath.org/ticket/9944#comment:33
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.1.alpha0</em>
</li>
</ul>
TicketjdemeyerThu, 05 May 2011 20:50:53 GMTstatus changed; work_issues set; resolution, merged deleted
https://trac.sagemath.org/ticket/9944#comment:34
https://trac.sagemath.org/ticket/9944#comment:34
<ul>
<li><strong>status</strong>
changed from <em>closed</em> to <em>new</em>
</li>
<li><strong>resolution</strong>
<em>fixed</em> deleted
</li>
<li><strong>work_issues</strong>
set to <em>fix on 32-bit</em>
</li>
<li><strong>merged</strong>
<em>sage-4.7.1.alpha0</em> deleted
</li>
</ul>
<p>
For some obscure reason, this breaks the following test on 32-bit systems:
</p>
<pre class="wiki">sage -t "devel/sage-main/sage/modular/abvar/morphism.py"
</pre><p>
The problem is that the following command hangs forever:
</p>
<pre class="wiki">sage: J = J1(12345)
sage: J.hecke_operator(997)
</pre><p>
Interestingly, interrupting at this point makes the command return the <strong>correct output</strong> without raising a <code>KeyboardInterrupt</code> which is a bug within the bug.
</p>
TicketSimonKingThu, 05 May 2011 21:15:50 GMT
https://trac.sagemath.org/ticket/9944#comment:35
https://trac.sagemath.org/ticket/9944#comment:35
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:34" title="Comment 34">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
For some obscure reason, this breaks the following test on 32-bit systems:
The problem is that the following command hangs forever:
</p>
<pre class="wiki">sage: J = J1(12345)
sage: J.hecke_operator(997)
</pre></blockquote>
<p>
Interesting. If I remember correctly, I had problems with that exact doctest on my machine and was able to solve it. But my machine is 64 bit.
</p>
<p>
So, I'll try with a 32 bit installation on bsd.math.
</p>
TicketSimonKingThu, 05 May 2011 21:24:21 GMT
https://trac.sagemath.org/ticket/9944#comment:36
https://trac.sagemath.org/ticket/9944#comment:36
<p>
I get a different error on bsd.math in 32bit mode:
</p>
<pre class="wiki">sage: J = J1(12345)
sage: J.hecke_operator(997)
python(6506) malloc: *** mmap(size=1870024854642688) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
python(6506) malloc: *** mmap(size=1870024854642688) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
Hecke operator T_997 on Abelian variety J1(12345) of dimension 5405473
</pre><p>
So, it reports problem with memory allocation, but in almost no time it still returns the correct answer!
</p>
TicketSimonKingFri, 06 May 2011 07:19:06 GMT
https://trac.sagemath.org/ticket/9944#comment:37
https://trac.sagemath.org/ticket/9944#comment:37
<p>
I think I remember what turned out to be the problem: In <code>J.hecke_operator(...)</code>, some matrix space is created - a very big one (kind of 5405473x5405473). And if I am not mistaken, the changes in the patch make the matrix space create a zero and a unit matrix - perhaps too much for 32 bit.
</p>
<p>
But perhaps I <em>am</em> mistaken. After all, the memory consumption is not big at all when I do the computation on my computer.
</p>
TicketjdemeyerFri, 06 May 2011 07:27:57 GMT
https://trac.sagemath.org/ticket/9944#comment:38
https://trac.sagemath.org/ticket/9944#comment:38
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:36" title="Comment 36">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
So, it reports problem with memory allocation, but in almost no time it still returns the correct answer!
</p>
</blockquote>
<p>
The fact that errors (including interrupts) are ignored in this code is very bad in itself, I think there must be some <code>except:</code> catching all this.
</p>
TicketSimonKingFri, 06 May 2011 07:54:05 GMT
https://trac.sagemath.org/ticket/9944#comment:39
https://trac.sagemath.org/ticket/9944#comment:39
<p>
Using <code>trace</code>, it seems to me that the error occurs in line 245 of <code>sage/matrix/matrix_space.py</code>:
</p>
<pre class="wiki">if nrows >= 2**63 or ncols >= 2**63:
</pre><p>
Is computing <code>2**63</code> (with Python ints) a problem on 32 bit?? Apparently not:
</p>
<pre class="wiki">sage: int(2)**int(63)
9223372036854775808L
</pre><p>
So, the problem isn't solved, yet.
</p>
TicketSimonKingFri, 06 May 2011 07:57:34 GMT
https://trac.sagemath.org/ticket/9944#comment:40
https://trac.sagemath.org/ticket/9944#comment:40
<p>
Sorry, I had misinterpreted something.
</p>
TicketSimonKingFri, 06 May 2011 07:59:24 GMT
https://trac.sagemath.org/ticket/9944#comment:41
https://trac.sagemath.org/ticket/9944#comment:41
<p>
But there is something else:
</p>
<pre class="wiki">sage: sage.misc.misc.is_64_bit
True
sage: os.environ['SAGE64']
'no'
</pre><p>
Could that be the problem?
</p>
TicketSimonKingFri, 06 May 2011 08:41:58 GMT
https://trac.sagemath.org/ticket/9944#comment:42
https://trac.sagemath.org/ticket/9944#comment:42
<p>
It seems that trace does not show the whole story. I see that some memory errors are raise (when it is attempted to create huge zero or unit matrices), but I don't see where they are caught. So, there seems Cython code involved that is invisible to trace.
</p>
TicketSimonKingFri, 06 May 2011 13:20:36 GMT
https://trac.sagemath.org/ticket/9944#comment:43
https://trac.sagemath.org/ticket/9944#comment:43
<p>
I think I found it!
</p>
<p>
The problem occurs during initialisation of <code>sage.modular.abvar.homspace.EndomorphismSubring</code>. It is first initialised as a homset with a specific category <code>cat</code> that does not belong to the category of rings, and then as a ring. The second initialisation tries to put it into the category of rings, which seems to be a bad idea after the first initialisation.
</p>
<p>
Solution:
</p>
<p>
Form the join of <code>cat</code> with the category of rings. Initialise it as a ring with that join category (which became possible with <a class="closed ticket" href="https://trac.sagemath.org/ticket/9944" title="defect: categories for polynomial rings (closed: fixed)">#9944</a>!). Eventually, initialise it as a homspace, with the same category.
</p>
<p>
With that little magic, the error seems to disappear. But now I need to do tests.
</p>
<p>
Cheers,
</p>
<p>
Simon
</p>
TicketSimonKingFri, 06 May 2011 13:41:21 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_abvar_endomorphism.patch</em>
</li>
</ul>
<p>
Fix a problem with initialisation of endomorphism rings of abelian varieties on 32 bit
</p>
TicketSimonKingFri, 06 May 2011 13:49:07 GMTstatus, description changed; work_issues deleted
https://trac.sagemath.org/ticket/9944#comment:44
https://trac.sagemath.org/ticket/9944#comment:44
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=44">diff</a>)
</li>
<li><strong>work_issues</strong>
<em>fix on 32-bit</em> deleted
</li>
</ul>
<p>
The problem seems solved.
</p>
<p>
What I did: Initialise the endomorphism ring first as a ring, and provide it with the intended category. Then initialise it as a homset as well. That solves the problem in the sense that it disappears.
</p>
<p>
Admittedly I can not explain how exactly the problem has originally emerged. But I guess it makes sense that it is a problem if a homset gives itself a certain category and then sage.rings.ring.Ring tries to work with another category.
</p>
<p>
With the new patch, we have (also as an additional doc test)
</p>
<pre class="wiki">sage: J = J1(12345)
sage: J.endomorphism_ring()
Endomorphism ring of Abelian variety J1(12345) of dimension 5405473
</pre><p>
both on my machine (x86_64 Linux) and on bsd.math in a 32 bit installation. Moreover, on both machines, the tests in sage.modular pass.
</p>
<p>
Needs review, I guess.
</p>
<p>
Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_polynomial_speedup.patch trac9944_abvar_endomorphism.patch
</p>
TicketSimonKingFri, 06 May 2011 15:41:11 GMT
https://trac.sagemath.org/ticket/9944#comment:45
https://trac.sagemath.org/ticket/9944#comment:45
<p>
FWIW: The long doctests pass on bsd.math in 32bit installation.
</p>
TicketjdemeyerSat, 07 May 2011 18:46:05 GMT
https://trac.sagemath.org/ticket/9944#comment:46
https://trac.sagemath.org/ticket/9944#comment:46
<p>
The patch at <a class="closed ticket" href="https://trac.sagemath.org/ticket/11310" title="enhancement: Monkey-patch catchall `except:` statements so they at least don't ... (closed: fixed)">#11310</a> solves the "exceptions are ignored" problem.
</p>
TicketjdemeyerSun, 08 May 2011 10:10:06 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:47
https://trac.sagemath.org/ticket/9944#comment:47
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
There is a huge performance regression in creating iterated polynomial rings:
</p>
<p>
BEFORE:
</p>
<pre class="wiki">sage: S = GF(9,'a')
sage: %time for n in range(11): S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
</pre><p>
AFTER:
</p>
<pre class="wiki">sage: S = GF(9,'a')
sage: %time for n in range(11): S = PolynomialRing(S,'w')
CPU times: user 53.38 s, sys: 0.19 s, total: 53.57 s
Wall time: 53.58 s
</pre>
TicketSimonKingSun, 08 May 2011 11:20:28 GMT
https://trac.sagemath.org/ticket/9944#comment:48
https://trac.sagemath.org/ticket/9944#comment:48
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:47" title="Comment 47">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
There is a huge performance regression in creating iterated polynomial rings:
...
sage: %time for n in range(11): S = <a class="missing wiki">PolynomialRing?</a>(S,'w')
</p>
</blockquote>
<p>
Note that the whole point of this ticket is to do more things during initialisation of polynomial rings. So, no surprise that initialisation becomes a lot slower. However, I agree that it should not be <em>that</em> slow.
</p>
TicketSimonKingSun, 08 May 2011 11:23:18 GMT
https://trac.sagemath.org/ticket/9944#comment:49
https://trac.sagemath.org/ticket/9944#comment:49
<p>
Strange. With the patches, I get
</p>
<pre class="wiki">sage: S = GF(9,'a')
sage: %time for n in range(5): S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
</pre><p>
So, that's quick. Continuing:
</p>
<pre class="wiki">sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 8.38 s, sys: 0.00 s, total: 8.38 s
Wall time: 8.38 s
</pre><p>
So, suddenly there is a jump in the initialisation time.
</p>
TicketSimonKingSun, 08 May 2011 11:28:22 GMT
https://trac.sagemath.org/ticket/9944#comment:50
https://trac.sagemath.org/ticket/9944#comment:50
<p>
Sorry, my fault. I did not restart before doing the test above, so, rings were found in the cache.
</p>
<p>
After restart with all patches, I get
</p>
<pre class="wiki">sage: S = GF(9,'a')
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.01 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.01 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.01 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.03 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.10 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.22 s, sys: 0.00 s, total: 0.22 s
Wall time: 0.22 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 0.70 s, sys: 0.00 s, total: 0.70 s
Wall time: 0.70 s
sage: %time S = PolynomialRing(S,'w')
CPU times: user 2.58 s, sys: 0.00 s, total: 2.58 s
Wall time: 2.58 s
</pre><p>
I found that the problem comes up with <a class="missing attachment">trac9944-polynomial_speedup.patch</a>. So, let's work on it.
</p>
TicketSimonKingSun, 08 May 2011 11:42:45 GMT
https://trac.sagemath.org/ticket/9944#comment:51
https://trac.sagemath.org/ticket/9944#comment:51
<p>
Using prun, I found for one case:
</p>
<pre class="wiki"> Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.141 0.141 0.238 0.238 polynomial_ring.py:178(__init__)
1414 0.055 0.000 0.071 0.000 polynomial_ring.py:234(_element_constructor_)
11104 0.020 0.000 0.020 0.000 polynomial_ring.py:1821(modulus)
1420 0.005 0.000 0.005 0.000 finite_field_givaro.py:153(degree)
...
</pre><p>
In other words: In order to construct just <em>one</em> polynomial ring over an iterated polynomial ring, the element constructor is called 1414 times and the modulus method 11104 times. At a different ticket, I suggested to turn the modulus method into a cached method. Perhaps that should already be done here. However, there should be no need to construct 1414 elements, just to initialise one ring!
</p>
TicketSimonKingSun, 08 May 2011 11:50:55 GMT
https://trac.sagemath.org/ticket/9944#comment:52
https://trac.sagemath.org/ticket/9944#comment:52
<p>
Interesting. Now it seems to me that the element constructor is in fact called from the <code>_repr_</code> method of <code>sage.rings.polynomial.polynomial_element.Polynomial_generic_dense</code>. That sound like using the string representation of elements in order to convert something.
</p>
TicketSimonKingSun, 08 May 2011 14:44:10 GMT
https://trac.sagemath.org/ticket/9944#comment:53
https://trac.sagemath.org/ticket/9944#comment:53
<p>
I think I somehow located the problem. I created recursively a univariate polynomial ring, as in your example, with a total of 8 variables:
</p>
<pre class="wiki">sage: S
Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Univariate Polynomial Ring in w over Finite Field in a of size 3^2
</pre><p>
Then, with the patches
</p>
<pre class="wiki">sage: timeit("S(0)")
5 loops, best of 3: 83 ms per loop
</pre><p>
but without the patches
</p>
<pre class="wiki">sage: timeit("S(0)")
625 loops, best of 3: 121 µs per loop
</pre><p>
Since the above relies on coercion maps, which are compositions of polynomial base injection maps, and since my patch touched the polynomial base injection maps, it is conceivable that we'll find the problem there.
</p>
<p>
Note, however, that it might be a better solution to let the composition of two polynomial base injection maps be another polynomial base injection map -- that ought to be a lot faster than a composite map.
</p>
TicketSimonKingMon, 09 May 2011 07:43:20 GMT
https://trac.sagemath.org/ticket/9944#comment:54
https://trac.sagemath.org/ticket/9944#comment:54
<p>
The original implementation of a polynomial basering injection relies on a method <code>_new_constant_poly</code>, which turns out to be rather slow in most cases except the case of dense univariate polynomials -- they have a custom version of <code>_new_constant_poly</code>, while the others rely on a generic implementation.
</p>
<p>
So, instead of my former suggestion ("use <code>one._rmul_(x)</code> to coerce x into P with <code>one = P.one_element()</code>), it may be better to provide the other polynomial classes with a faster implementation of <code>_new_constant_poly</code>. That's what I am trying now.
</p>
TicketSimonKingMon, 09 May 2011 09:54:27 GMT
https://trac.sagemath.org/ticket/9944#comment:55
https://trac.sagemath.org/ticket/9944#comment:55
<p>
Or, even better: Implement <code>_new_constant_poly</code> not (only) for the <em>elements</em> of a polynomial ring, but for the ring itself - that should be more natural, provided that there is only one possible polynomial class.
</p>
TicketSimonKingThu, 12 May 2011 06:42:05 GMT
https://trac.sagemath.org/ticket/9944#comment:56
https://trac.sagemath.org/ticket/9944#comment:56
<p>
I am totally frustrated.
</p>
<p>
I made some improvements to <code>_new_constant_poly</code>, whose purpose is to provide the quickest way in the given implementation to construct a constant polynomial, and made some other changes that should improve the coercions. There were improvements in all examples above.
</p>
<p>
However, I am now getting tons of failures and even segfaults in sage/schemes.
</p>
<p>
I tracked one type of error down, I thought. But apparently I only covered one special case of that one type of error.
</p>
<p>
While I was at it, I fixed the documentation for <code>hyperelliptic_padic_field</code>, which is not yet included into the manual, and which had syntax errors in all doc strings.
</p>
TicketSimonKingThu, 12 May 2011 06:45:32 GMT
https://trac.sagemath.org/ticket/9944#comment:57
https://trac.sagemath.org/ticket/9944#comment:57
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:56" title="Comment 56">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
While I was at it, I fixed the documentation for <code>hyperelliptic_padic_field</code>, which is not yet included into the manual, and which had syntax errors in all doc strings.
</p>
</blockquote>
<p>
Or perhaps the inclusion of sage/schemes into the manual should be on a different ticket, since most files are missing.
</p>
TicketSimonKingFri, 13 May 2011 05:49:18 GMT
https://trac.sagemath.org/ticket/9944#comment:58
https://trac.sagemath.org/ticket/9944#comment:58
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:56" title="Comment 56">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
I am totally frustrated.
</p>
</blockquote>
<p>
Still the case, although I am already down to 251 doctest failures and one timeout. That's the disadvantage of doing changes in coercion.
</p>
TicketSimonKingFri, 13 May 2011 15:44:45 GMTstatus, description changed; dependencies set
https://trac.sagemath.org/ticket/9944#comment:59
https://trac.sagemath.org/ticket/9944#comment:59
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>sage-4.7</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=59">diff</a>)
</li>
</ul>
<p>
Finally I got my new patch to work. Here are the new features and, in particular, the new timings. I think it was worth the effort!
</p>
<p>
<span class="underline">Polynomial Construction Functors</span>
</p>
<pre class="wiki">sage: R.<x> = PolynomialRing(GF(5), sparse=True)
sage: F,B = R.construction()
sage: F(B) is R
True # was False
</pre><p>
<span class="underline">zero_element</span>
</p>
<p>
In various places, constructions such as self.parent()(0) are used. It should be more efficient to have self.parent().zero_element() instead, in particular if this is cached using the improved cached methods from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11115" title="enhancement: Rewrite cached_method in Cython (closed: fixed)">#11115</a>.
</p>
<p>
That means I had to introduce zero_element() for various classes, mostly in sage/modular.
</p>
<p>
<span class="underline">Fix zero element of free module homomorphisms</span>
</p>
<p>
The following used to fail with an error:
</p>
<pre class="wiki">sage: V = span([[1/2,1,1],[3/2,2,1],[0,0,1]],ZZ)
sage: V.Hom(V).zero()
Free module morphism defined by the matrix
[0 0 0]
[0 0 0]
[0 0 0]
Domain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...
Codomain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...
</pre><p>
<span class="underline">Calling any parent with None should return zero</span>
</p>
<p>
This used to be true for finite prime fields, but failed with an error
for finite non-prime fields:
</p>
<pre class="wiki">sage: GF(5)(None)
0
sage: GF(5^2,'a')(None)
0
</pre><p>
<span class="underline">Implement/improve <code>_new_constant_poly</code> for various polynomial classes</span>
</p>
<p>
This is the main reason why the timings stated below have improved. I thought that <code>_new_constant_poly</code> should be a method of a polynomial ring, but I think it should better stay as a method of polynomials: Polynomials are often implemented in Cython, but polynomial rings in Python.
</p>
<p>
In order to get a little bit of more speed, I introduce another parameter to <code>_new_constant_poly</code>, namely the parent in which the new polynomial is supposed to be created. This is because often the parent <code>P</code> of a polynomial <code>self</code> is already known when calling <code>self._new_constant_poly(a, P)</code>, so that it would be a waste of time to call <code>self.parent()</code> internally to determine the parent.
</p>
<p>
<span class="underline">Improve Polynomial Base Injection Morphisms and use it for coercion</span>
</p>
<p>
Conversion into a polynomial ring P from its base ring occurs frequently and should be as quick as possible.
</p>
<p>
I had already improved the performance in the old patch version. However, it turned out to be better to use <code>_new_constant_poly</code>, rather than always using multiplication with <code>P.one()</code>.
</p>
<p>
The rule is now: If <code>P.an_element()</code> has a <code>_new_constant_poly</code> method then it is used. Otherwise, if one can construct a one element in <code>P</code> without calling coercion, and if it has <code>_rmul_</code> and if <code>_rmul_</code> does not return <code>None</code> then it is used. Otherwise, <code>P._element_constructor_</code> is used.
</p>
<p>
Polynomial base injection morphisms are now always registered as coercion.
</p>
<p>
<span class="underline">Call method for compiled polynomials</span>
</p>
<p>
The documentation for compiled polynomials states that it can be called, although the cdef method <code>.eval(...)</code> has less overhead. That was not true, there has been no <code>__call__</code> method. I added one.
</p>
<p>
<span class="underline">Constant polynomial section</span>
</p>
<p>
It was stated that it uses the <code>constant_coefficient</code> method, which can be optimized for a particulare polynomial type. However, in fact a generic <code>constant_coefficient</code> method was <strong>explicitly</strong> called, even if a polynomial type did provide a more efficient method. That has now changed.
</p>
<p>
<span class="underline">Sparse versus dense versus differently implemented polynomial rings</span>
</p>
<p>
A univariate polynomial ring can be sparse or dense, and if it is dense and over <code>ZZ</code> (or also <code>QQ</code>) they can be implemented with <code>FLINT</code> or <code>NTL</code>. Dense and sparse rings used to be equal, but they were not identical - a violation to the unique parent assumption.
</p>
<p>
Moreover, in the multivariate case, the <code>implementation</code> and <code>sparse</code> arguments had no effect on the resulting ring, but were used in the cache key, yielding another violation of the unique parent assumption.
</p>
<p>
I resolved these violations. I was not sure whether one should silently ignore arguments that are not used, or should raise an error if they are provided. I decided to ignore <code>sparse</code> if it is not supported, and raise an error for dense or multivariate rings if an implementation is not supported.
</p>
<p>
We have, e.g.:
</p>
<pre class="wiki">sage: S.<x,y> = PolynomialRing(ZZ,sparse=True)
sage: S is ZZ['x','y']
True # used to be False
sage: R.<x> = PolynomialRing(ZZ,sparse=True,implementation='FLINT')
sage: S.<x> = PolynomialRing(ZZ,sparse=True,implementation='NTL')
sage: R is S
True # used to be False
sage: R == ZZ['x']
False # used to be True
sage: S.<x,y> = PolynomialRing(ZZ, implementation='NTL')
Traceback (most recent call last):
...
ValueError: The NTL implementation is not known for multivariate polynomial rings
</pre><p>
The last example used to return a ring that was equal but not identic to <code>ZZ['x','y']</code>!
</p>
<p>
Polynomial rings are now equal if and only if they are identical. Coercions exist from the non-default to the default version of a ring (hence, from sparse to dense, from NTL to FLINT.
</p>
<pre class="wiki">sage: R.<x> = PolynomialRing(ZZ)
sage: S.<x> = PolynomialRing(ZZ, implementation='NTL')
sage: R == S
False
sage: R.has_coerce_map_from(S)
True
sage: S.has_coerce_map_from(R)
False
sage: S.<x> = PolynomialRing(ZZ, sparse=True)
sage: R == S
False
sage: R.has_coerce_map_from(S)
True
sage: S.has_coerce_map_from(R)
False
</pre><p>
By consequence, the parent of a sum of polynomials is now unique - it used to depend on the summation order if dense and sparse summands were involved.
</p>
<p>
<span class="underline">Documentation and examples</span>
</p>
<p>
I think all changes are covered by doctests. Occasionally I fixed wrongly formatted docstrings.
</p>
<p>
<span class="underline">Performance</span>
</p>
<p>
Here are the new timings for the examples that we had discussed above. I use sage-4.7.alpha5 with the patches from this ticket applied, and I compare with timings that I had obtained with an unpatched version of sage-4.7.alpha5
</p>
<p>
There is no significant change in the startup time: I got <code>1.253</code> for sage.all in unpatched sage, but the margin of error seems rather wide.
</p>
<pre class="wiki">$ sage -startuptime
...
== Slowest (including children) ==
1.100 sage.all (None)
0.279 sage.schemes.all (sage.all)
0.178 twisted.persisted.styles (sage.all)
0.164 elliptic_curves.all (sage.schemes.all)
0.162 ell_rational_field (elliptic_curves.all)
0.150 ell_number_field (ell_rational_field)
...
</pre><p>
Here is the example brought up by Jeroen. There is now a drastic speedup were previously was a drastic slow down:
</p>
<pre class="wiki">sage: S = GF(9,'a')
sage: %time for n in range(8): S = PolynomialRing(S,'w')
CPU times: user 0.03 s, sys: 0.00 s, total: 0.03 s
Wall time: 0.03 s
# unpatched: 0.04 s
sage: len(S.variable_names_recursive())
8
sage: timeit("S(0)")
625 loops, best of 3: 27.9 µs per loop
# with only the other patches: 83 ms
# unpatched: 121 µs
</pre><p>
Here is the example brought up by Martin Raum:
</p>
<pre class="wiki">sage: R = PolynomialRing(ZZ, ['a' + str(n) for n in range(10000)])
sage: x = R.gen(0)
sage: timeit('(2*x - 1)^2 + 5', number = 10^4)
10000 loops, best of 3: 58.2 µs per loop
# unpatched: 66.9 µs
</pre><p>
Here are the arithmetic examples that I had provided earlier:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.58 µs per loop
# unpatched: 23.6 µs
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 8.4 µs per loop
# unpatched: 25.8 µs
sage: R.<x> = GF(3)[] # sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 66.4 µs per loop
# unpatched: 90.1 µs
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 75.4 µs per loop
# unpatched: 117 µs
sage: R.<x,y> = ZZ[] # sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 7.85 µs per loop
# unpatched: 13.6 µs
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 7.33 µs per loop
# unpatched: 16.9 µs
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 6.59 µs per loop
# unpatched: 11.2 µs
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 158 µs per loop
# unpatched: 251 µs
sage: R.<x,y> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 488 µs per loop
# unpatched: 521 µs
sage: R.<x> = Qp(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 894 µs per loop
# unpatched: 1.06 ms
sage: R.<x> = PolynomialRing(GF(9,'a'), sparse=True)
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 236 µs per loop
# unpatched: 265 µs
</pre><p>
So, in <strong>all</strong> examples there is a noticeable speedup.
</p>
<p>
<span class="underline">Conclusion</span>
</p>
<p>
The new patch cleans coercion of polynomial rings, by enforcing uniqueness of parents.
</p>
<p>
It considerably improves the performance, even when comparing with the improvements that were introduced in the previous patches.
</p>
<p>
<code>sage -testall -long</code> passed. So, it is finally ready for review again.
</p>
<p>
Depends on sage-4.7
</p>
<p>
Apply Apply 9944-poly-cat.patch 9944-poly-cat-doctests.patch trac-9944-poly-cat-review.patch trac9944_polynomial_speedup.patch trac9944_abvar_endomorphism.patch trac9944_faster_and_cleaner_coercion.patch
</p>
TicketSimonKingFri, 13 May 2011 17:02:21 GMT
https://trac.sagemath.org/ticket/9944#comment:60
https://trac.sagemath.org/ticket/9944#comment:60
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:59" title="Comment 59">SimonKing</a>:
</p>
<blockquote class="citation">
<blockquote>
<p>
...
<span class="underline">Improve Polynomial Base Injection Morphisms and use it for coercion</span>
</p>
</blockquote>
<p>
...
</p>
<blockquote>
<p>
The rule is now: If <code>P.an_element()</code> has a <code>_new_constant_poly</code> method then it is used. Otherwise, if one can construct a one element in <code>P</code> without calling coercion, and if it has <code>_rmul_</code> and if <code>_rmul_</code> does not return <code>None</code> then it is used. Otherwise, <code>P._element_constructor_</code> is used.
</p>
</blockquote>
</blockquote>
<p>
I stand corrected. The above rule did hold for an intermediate (unpublished) patch version. With the new patch, all polynomial classes have <code>_new_constant_poly</code>, and it will <em>always</em> be used for basering injection.
</p>
<p>
Hence, there is a return statement after getting <code>_new_constant_poly</code>, and the subsequent lines of <code>sage.rings.polynomial.polynomial_element.PolynomialBaseInjection.__init__</code> will never be executed. I will remove them in the final patch version, but I first wait for input of a referee.
</p>
TicketjdemeyerMon, 16 May 2011 08:00:00 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:61
https://trac.sagemath.org/ticket/9944#comment:61
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=61">diff</a>)
</li>
</ul>
TicketjdemeyerMon, 16 May 2011 08:59:14 GMTstatus, dependencies changed
https://trac.sagemath.org/ticket/9944#comment:62
https://trac.sagemath.org/ticket/9944#comment:62
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>dependencies</strong>
changed from <em>sage-4.7</em> to <em>sage-4.7 + #11139</em>
</li>
</ul>
<p>
Please rebase the last patch to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>.
</p>
TicketmraumMon, 16 May 2011 09:22:40 GMT
https://trac.sagemath.org/ticket/9944#comment:63
https://trac.sagemath.org/ticket/9944#comment:63
<p>
This should clearly be reviewed as quick as possible, since otherwise it will need frequent rebaseing. I just don't have the time to do it all, but if anybody was willing to share the effort, I could spend some time on this in the next two or three days.
</p>
TicketmraumMon, 16 May 2011 11:00:22 GMT
https://trac.sagemath.org/ticket/9944#comment:64
https://trac.sagemath.org/ticket/9944#comment:64
<p>
So far I read till sage/rings/polynomial/laurent_polynomial_ring.py in the order that the patch is printed. Only one issue here:
in free_module_homspace.py l.128 (new counting) a doctest is missing that checks that passing a function works fine.
</p>
<p>
Simon, if you rebase this, could you also upload a diff file for the new and old patch? That would make my and possibly the life of all others easier.
</p>
<p>
Martin
</p>
<p>
PS: I am still building 4.7, so I haven't run any tests yet.
</p>
TicketSimonKingMon, 16 May 2011 11:14:49 GMT
https://trac.sagemath.org/ticket/9944#comment:65
https://trac.sagemath.org/ticket/9944#comment:65
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:64" title="Comment 64">mraum</a>:
</p>
<blockquote class="citation">
<p>
So far I read till sage/rings/polynomial/laurent_polynomial_ring.py in the order that the patch is printed. Only one issue here:
in free_module_homspace.py l.128 (new counting) a doctest is missing that checks that passing a function works fine.
</p>
</blockquote>
<p>
It <strong>is</strong> tested. The patch has added the following test:
</p>
<pre class="wiki">
sage: V = span([[1/2,1,1],[3/2,2,1],[0,0,1]],ZZ)
sage: V.Hom(V).zero()
Free module morphism defined by the matrix
[0 0 0]
[0 0 0]
[0 0 0]
Domain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...
Codomain: Free module of degree 3 and rank 3 over Integer Ring
Echelon ...
</pre><p>
In unpatched sage-4.7.alpha5, you would get
</p>
<pre class="wiki">ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (396, 0))
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (6924, 0))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
...
TypeError: 'function' object is not iterable
</pre><blockquote class="citation">
<p>
Simon, if you rebase this, could you also upload a diff file for the new and old patch? That would make my and possibly the life of all others easier.
</p>
</blockquote>
<p>
OK.
</p>
TicketSimonKingMon, 16 May 2011 11:22:16 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:66
https://trac.sagemath.org/ticket/9944#comment:66
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Patch's up!
</p>
<p>
For the record: I started with sage-4.7.alpha5, then the first five patches from here, then from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>, and finally the sixth patch from here.
</p>
<p>
I verified that the tests of sage.rings.ring pass, because that is what was modified, and sage.rings.ideal, because that is what the modification from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a> is about.
</p>
TicketSimonKingMon, 16 May 2011 11:24:22 GMT
https://trac.sagemath.org/ticket/9944#comment:67
https://trac.sagemath.org/ticket/9944#comment:67
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:66" title="Comment 66">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Patch's up!
</p>
</blockquote>
<p>
And diff file as well.
</p>
TicketmraumMon, 16 May 2011 19:42:30 GMT
https://trac.sagemath.org/ticket/9944#comment:68
https://trac.sagemath.org/ticket/9944#comment:68
<p>
With a freshly built 4.7 I get a reject in polynomial_element.pyx. This only concerns the doctest for the <a class="missing wiki">BaseringInjection?</a>, so for the moment I leave it as it is and I run tests.
</p>
TicketSimonKingTue, 17 May 2011 21:01:01 GMT
https://trac.sagemath.org/ticket/9944#comment:69
https://trac.sagemath.org/ticket/9944#comment:69
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:68" title="Comment 68">mraum</a>:
</p>
<blockquote class="citation">
<p>
With a freshly built 4.7 I get a reject in polynomial_element.pyx.
</p>
</blockquote>
<p>
Strange. I started with sage.4.7.alpha5, imported the patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a> (it is only one, if I am not mistaken), and then the patches apply cleanly for me. Is there another merged ticket that interferes?
</p>
TicketmraumTue, 17 May 2011 21:57:08 GMT
https://trac.sagemath.org/ticket/9944#comment:70
https://trac.sagemath.org/ticket/9944#comment:70
<p>
For the record: I'm at sage/rings/polynomial/polynomial_zmod_flint.pxd
</p>
<p>
Simon, you are completely right about the doctest with span. Could we add #indirect doctest so that attention is drawn to this?
</p>
<p>
Some issues, that I encountered:
in polynomial_element.pxy new line 5352 : what about p-adics? I haven't had the time to check, but perhaps you can already say something about it.
in polynomial_element.pxy new line 6180ff : there are two returns that do not belong there
</p>
<p>
in polynomial_real_mpfr_dense.pxy new line 57: Do you mean [0]?
in polynomial_ring.py new line 468 : The coercing is the other way around.
</p>
<p>
Please don't forget to check the rejects that I've mentioned above. This could be a real problem for Jeroen.
</p>
<p>
So far, these are amazingly few issues for such a huge patch!
</p>
<p>
Hope to continue this by tomorrow (night).
</p>
<p>
Martin
</p>
TicketmraumWed, 18 May 2011 06:33:35 GMT
https://trac.sagemath.org/ticket/9944#comment:71
https://trac.sagemath.org/ticket/9944#comment:71
<p>
hg blame gives me that some changes were, for example, made to denominator. My last tags are 15689, so my version is the same as 4.7rc2.
</p>
TicketSimonKingWed, 18 May 2011 07:25:27 GMT
https://trac.sagemath.org/ticket/9944#comment:72
https://trac.sagemath.org/ticket/9944#comment:72
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:70" title="Comment 70">mraum</a>:
</p>
<blockquote class="citation">
<p>
Simon, you are completely right about the doctest with span. Could we add #indirect doctest so that attention is drawn to this?
</p>
</blockquote>
<p>
OK, and perhaps I even add a comment like "The method zero() calls this hom space with a function, not with a matrix, and that case had previously not been taken care of".
</p>
<blockquote class="citation">
<p>
Some issues, that I encountered:
in polynomial_element.pxy new line 5352 : what about p-adics? I haven't had the time to check, but perhaps you can already say something about it.
</p>
</blockquote>
<p>
You mean the fact that I return <code><Polynomial>self._parent(self[:n])</code> when it previously was <code><Polynomial>self._parent(self[:n], check=False)</code>?
</p>
<p>
I tried to reconstruct what made me do that change. It now seems to me that it was not because of a bug but because I thought <code>self[:n]</code> would return a truncated list of coefficients, which apparently is not the case (at least not always).
</p>
<p>
Anyway. <em>If</em> you feed a truncated list of coefficients into the element constructor of a univariate polynomial ring, and if you give <code>check=False</code>, then you could create a polynomial whose list of coefficients ends with a zero. That is a problem for non-padic polynomials, since <code>valuation()</code> and other methods will result in an error.
</p>
<p>
So, <code>if</code> there are polynomials p so that <code>p[:n]</code> returns the list of the first n coefficients, then <code>check=False</code> is a bug.
</p>
<p>
However, if <code>p[:n]</code> returns a polynomial that actually has the right parent, then the argument <code>check</code> will not be tested at all. So, <code>False</code> or <code>True</code> does not matter.
</p>
<p>
<strong>Conclusion:</strong> Removing <code>check=True</code> should have no influence on performance, but may fix a potential problem (depending on the behaviour of <code>p[:n]</code>).
</p>
<p>
In any case, it can not be a problem for padics, even <em>if</em> <code>self[:n]</code> returns a list: I do not remove trailing zeroes from the coefficient list, but simply let the element constructor of <code>self._parent</code> decide what to do -- and the element constructor of padic and non-padic polynomial rings will do the right thing.
</p>
<p>
Here is a padic example:
</p>
<pre class="wiki">sage: P.<x> = Zp(5)[]
sage: p = x^4
sage: p.truncate(3).valuation()
+Infinity
</pre><p>
and that is because <code>p[:3].parent() is P</code>.
</p>
<p>
I just found that the existing test for the <code>truncate</code> method in <code>sage.rings.polynomial.polynomial_element</code> does <em>not</em> test that method. Namely:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]; S.<y> = R[]
sage: f = y^3 + x*y -3*x
sage: from sage.misc.sageinspect import sage_getfile, sage_getsourcelines
sage: sage_getfile(f.truncate)
'/mnt/local/king/SAGE/sage-4.7.alpha5/devel/sage/sage/rings/polynomial/polynomial_element.pyx'
sage: sage_getsourcelines(f.truncate)[1]
6000
</pre><p>
So, <code>f.truncate</code> is a different truncate method. I'll change that doctest by making S a sparse polynomial ring:
</p>
<pre class="wiki">sage: R.<x> = ZZ[]; S.<y> = PolynomialRing(R, sparse=True)
sage: f = y^3 + x*y -3*x
sage: sage_getfile(f.truncate)
'/mnt/local/king/SAGE/sage-4.7.alpha5/devel/sage/sage/rings/polynomial/polynomial_element.pyx'
sage: sage_getsourcelines(f.truncate)[1]
5335
</pre><blockquote class="citation">
<p>
in polynomial_element.pxy new line 6180ff : there are two returns that do not belong there
</p>
</blockquote>
<p>
Yep. See post 60. I promised to remove the lines starting with the comment <code># this is likely to be overridden below:</code> in the final patch version, but wanted to wait for input of a reviewer (thank you, reviewer!)
</p>
<blockquote class="citation">
<p>
in polynomial_real_mpfr_dense.pxy new line 57: Do you mean [0]?
</p>
</blockquote>
<p>
Yes, and I'm changing it, although <code>i</code> works as well:
</p>
<pre class="wiki">sage: from sage.rings.polynomial.polynomial_real_mpfr_dense import PolynomialRealDense
sage: PolynomialRealDense(RR['x'],None)
0
</pre><blockquote class="citation">
<p>
in polynomial_ring.py new line 468 : The coercing is the other way around.
</p>
</blockquote>
<p>
Thank you!
</p>
<blockquote class="citation">
<p>
Please don't forget to check the rejects that I've mentioned above. This could be a real problem for Jeroen.
</p>
</blockquote>
<p>
I'll try it, and will soon submit a new version of the last patch.
</p>
TicketSimonKingWed, 18 May 2011 07:41:40 GMT
https://trac.sagemath.org/ticket/9944#comment:73
https://trac.sagemath.org/ticket/9944#comment:73
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:71" title="Comment 71">mraum</a>:
</p>
<blockquote class="citation">
<p>
hg blame gives me that some changes were, for example, made to denominator. My last tags are 15689, so my version is the same as 4.7rc2.
</p>
</blockquote>
<p>
I went through all patches that where merged since 4.7.alpha5 according to <a class="ext-link" href="http://boxen.math.washington.edu/home/release/sage-4.7.rc2/tickets.html"><span class="icon"></span>http://boxen.math.washington.edu/home/release/sage-4.7.rc2/tickets.html</a>
</p>
<p>
I found no patch touching sage.rings.polynomial.polynomial_element.pyx, actually no patch that contains the word fragment "poly".
</p>
<p>
So, I am still puzzled. Perhaps the release manager can state what ticket (in addition to <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>) I have to take into account.
</p>
TicketjdemeyerWed, 18 May 2011 10:34:09 GMT
https://trac.sagemath.org/ticket/9944#comment:74
https://trac.sagemath.org/ticket/9944#comment:74
<p>
There shouldn't be any other patch to take into account (apart from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>). Could it be that you rebased to a non-clean sage-4.7.alpha5?
</p>
<p>
Actually, the best would be to rebase to <a class="ext-link" href="http://boxen.math.washington.edu/home/release/sage-4.7.1.alpha0/"><span class="icon"></span>http://boxen.math.washington.edu/home/release/sage-4.7.1.alpha0/</a>. It's not yet released, but it gives a good target for rebasing.
</p>
TicketjdemeyerWed, 18 May 2011 10:41:15 GMT
https://trac.sagemath.org/ticket/9944#comment:75
https://trac.sagemath.org/ticket/9944#comment:75
<p>
To be clear, I meant rebase to sage-4.7.1.alpha0 + <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>.
</p>
TicketSimonKingWed, 18 May 2011 12:22:08 GMT
https://trac.sagemath.org/ticket/9944#comment:76
https://trac.sagemath.org/ticket/9944#comment:76
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:74" title="Comment 74">jdemeyer</a>:
</p>
<blockquote class="citation">
<p>
There shouldn't be any other patch to take into account (apart from <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>). Could it be that you rebased to a non-clean sage-4.7.alpha5?
</p>
</blockquote>
<p>
I don't think so.
</p>
<p>
Anyway. I just finished the built of sage-4.7.rc2, and I found no problems at all with my patches. <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Attachment 'trac9944_polynomial_speedup.patch' in Ticket #9944">trac9944_polynomial_speedup.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Download"></a> succeeded with a little fuzz, but there has been no rejection.
</p>
<p>
Therefore I just submitted a new version of <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_faster_and_cleaner_coercion.patch" title="Attachment 'trac9944_faster_and_cleaner_coercion.patch' in Ticket #9944">trac9944_faster_and_cleaner_coercion.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_faster_and_cleaner_coercion.patch" title="Download"></a> that addresses Martin's comments, but the other patches can stay as they are, IMHO.
</p>
TicketSimonKingWed, 18 May 2011 14:05:25 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>9944diff</em>
</li>
</ul>
<p>
diff file for old and new patch version
</p>
TicketSimonKingWed, 18 May 2011 14:06:56 GMT
https://trac.sagemath.org/ticket/9944#comment:77
https://trac.sagemath.org/ticket/9944#comment:77
<p>
I also added the result of <code>diff trac9944_faster_and_cleaner_coercion.patch.orig trac9944_faster_and_cleaner_coercion.patch</code>, where <code>trac9944_faster_and_cleaner_coercion.patch.orig</code> is the patch version from before Mai 16, if that helps with the review.
</p>
TicketmraumWed, 18 May 2011 21:09:11 GMT
https://trac.sagemath.org/ticket/9944#comment:78
https://trac.sagemath.org/ticket/9944#comment:78
<p>
I'm done with reading. All tests (-long) passed, but with the latest version I want to try again. This might take some time.
</p>
<p>
I encountered only two further issues:
in polynomial_zz_pex.pyx new line 107f there is no specification of the except clause and I think raise <a class="missing wiki">TypeError?</a> ... is what belongs there. I know this is not your code, but it would be nice to fix this "on the fly". Can we have a doctest for this?
</p>
<p>
I don't understand the changes to qqbar.py. And also I have the feeling I saw this kind of change already. Have you, perhaps, confused this change? If not, could you say, why you made it?
</p>
<p>
There is still the issue with the rejects. Will you rebase to 4.7.1? In that case the problem might disappear. I will start compiling the latest version right now. So by tomorrow, if you could provide a rebased version and all tests pass, I can give this a positive review.
But already: Greate work!
</p>
<p>
Martin
</p>
TicketSimonKingThu, 19 May 2011 06:09:46 GMT
https://trac.sagemath.org/ticket/9944#comment:79
https://trac.sagemath.org/ticket/9944#comment:79
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:78" title="Comment 78">mraum</a>:
</p>
<blockquote class="citation">
<p>
I encountered only two further issues:
in polynomial_zz_pex.pyx new line 107f there is no specification of the except clause and I think raise <a class="missing wiki">TypeError?</a> ... is what belongs there. I know this is not your code, but it would be nice to fix this "on the fly". Can we have a doctest for this?
</p>
</blockquote>
<p>
I am trying. But probably you are right, it should probably be <code>except TypeError</code>.
</p>
<blockquote class="citation">
<p>
I don't understand the changes to qqbar.py. And also I have the feeling I saw this kind of change already. Have you, perhaps, confused this change? If not, could you say, why you made it?
</p>
</blockquote>
<p>
That change only concerns a doctest involving the function <code>sage_input</code>. Its purpose is to give a construction to any given object. Apparently, the coercion changes led to a different but equivalent construction in one of the examples.
</p>
<blockquote class="citation">
<p>
There is still the issue with the rejects.
</p>
</blockquote>
<p>
Is there really? Meanwhile I got sage-4.7.rc2, and I did <em>not</em> get any rejects for any of the patches. I merely got an "applied with fuzz", but that's not a reject. Are you sure that you started with a fresh sage-4.7.rc2, applied <a class="closed ticket" href="https://trac.sagemath.org/ticket/11139" title="defect: Ideal with no generators for univariate polynomial rings (closed: fixed)">#11139</a>, and then applied the 6 patches in order as listed in the ticket description, and only these? Please do not apply <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_second_referee.patch" title="Attachment 'trac9944_second_referee.patch' in Ticket #9944">trac9944_second_referee.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_second_referee.patch" title="Download"></a>, if that was the problem.
</p>
<blockquote class="citation">
<p>
Will you rebase to 4.7.1?
</p>
</blockquote>
<p>
I don't see the need, since it does apply to 4.7.rc2, IMHO.
</p>
<p>
Cheers,
Simon
</p>
TicketSimonKingThu, 19 May 2011 06:19:09 GMT
https://trac.sagemath.org/ticket/9944#comment:80
https://trac.sagemath.org/ticket/9944#comment:80
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:79" title="Comment 79">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:78" title="Comment 78">mraum</a>:
</p>
<blockquote class="citation">
<p>
I encountered only two further issues:
in polynomial_zz_pex.pyx new line 107f there is no specification of the except clause and I think raise <a class="missing wiki">TypeError?</a> ... is what belongs there. I know this is not your code, but it would be nice to fix this "on the fly". Can we have a doctest for this?
</p>
</blockquote>
<p>
I am trying. But probably you are right, it should probably be <code>except TypeError</code>.
</p>
</blockquote>
<p>
I think I misunderstood your remark: You do not complain about the fact that there is a bare <code>except</code>, but you noticed that the <a class="missing wiki">TypeError?</a> is constructed but not raised. That's odd, of course.
</p>
<p>
I found the following example, in which the error should be raised:
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: R([3,'1234'])
3*x + 3
</pre><p>
Hence, currently there is no error raised and the result is absolute nonsense.
</p>
<p>
I'll fix that.
</p>
TicketSimonKingThu, 19 May 2011 06:30:35 GMT
https://trac.sagemath.org/ticket/9944#comment:81
https://trac.sagemath.org/ticket/9944#comment:81
<p>
The bug in polynomial_zz_pex.pyx is fixed, and the fix is doctested.
</p>
<p>
But having done that, I wonder whether raising an error is really what we want in this example. After all, the semantics of <code>R(...)</code> is: "Make sense of the arguments, if possible at all - even if there is no coercion, there could still be a conversion."
</p>
<p>
So, here, <code>R([3,'1234'])</code> should perhaps better not result in an error but in <code>1234*x + 3</code>. What do you think?
</p>
TicketmraumThu, 19 May 2011 06:41:31 GMT
https://trac.sagemath.org/ticket/9944#comment:82
https://trac.sagemath.org/ticket/9944#comment:82
<p>
To me this sounds reasonable.
</p>
<p>
I have just made the changes to rebase to 4.7.1.alpha0. I think the point of Jeroen was that he will work with this version anyway and its only two tiny changes. Send your new patches, I will do the rebase and then I think Jeroen can imediatelly go for it (if he wants to).
</p>
TicketSimonKingThu, 19 May 2011 06:50:54 GMT
https://trac.sagemath.org/ticket/9944#comment:83
https://trac.sagemath.org/ticket/9944#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:82" title="Comment 82">mraum</a>:
</p>
<blockquote class="citation">
<p>
To me this sounds reasonable.
</p>
</blockquote>
<p>
What is "this"? Do you mean, raising an error is reasonable, or trying conversion rather than coercion is reasonable?
</p>
TicketSimonKingThu, 19 May 2011 08:38:00 GMT
https://trac.sagemath.org/ticket/9944#comment:84
https://trac.sagemath.org/ticket/9944#comment:84
<p>
I found another bug in polynomial_zz_pex.pyx:
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: R([3,x])
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (1154, 0))
Traceback (most recent call last):
...
TypeError: polynomial() takes exactly one argument (0 given)
</pre><p>
I suggest to not only catch an attribute error (namely when requesting <code>e.polynomial()</code>) but also a type error.
</p>
<p>
And my preference is to do try a conversion, before raising an error on a failing coercion. If that sounds reasonable to you then I'll submit an update of my patch.
</p>
TicketmraumThu, 19 May 2011 09:58:11 GMT
https://trac.sagemath.org/ticket/9944#comment:85
https://trac.sagemath.org/ticket/9944#comment:85
<p>
I would say this sounds indeed reasonable. No coercion was demanded for, so why to restrict to it. This was what you were talking about before, weren't you?
</p>
TicketSimonKingThu, 19 May 2011 10:45:27 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_faster_and_cleaner_coercion.patch</em>
</li>
</ul>
<p>
Enforce uniqueness of parents for polynomial rings; further perfomance improvement for coercion
</p>
TicketSimonKingThu, 19 May 2011 10:48:07 GMT
https://trac.sagemath.org/ticket/9944#comment:86
https://trac.sagemath.org/ticket/9944#comment:86
<p>
With the new patch version, we have
</p>
<pre class="wiki">sage: K.<a>=GF(next_prime(2**60)**3)
sage: R.<x> = PolynomialRing(K,implementation='NTL')
sage: R([3,'1234'])
1234*x + 3
sage: R([3,'12e34'])
Traceback (most recent call last):
...
TypeError: unable to convert '12e34' into the base ring
sage: R([3,x])
Traceback (most recent call last):
...
TypeError: unable to convert x into the base ring
</pre><p>
So, a conversion is attempted, and the error message is mentioning conversion and not coercion.
</p>
<p>
The tests of polynomial_zz_pex.pyx pass. I didn't test the rest of Sage.
</p>
TicketmraumThu, 19 May 2011 12:43:14 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_faster_and_cleaner_coercion.2.patch</em>
</li>
</ul>
<p>
Rebase to 4.7.1.alpha0
</p>
TicketmraumThu, 19 May 2011 12:43:51 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac-9944-polynomial_speedup.patch</em>
</li>
</ul>
<p>
Rebase to 4.7.1.alpha0
</p>
TicketmraumThu, 19 May 2011 12:47:37 GMT
https://trac.sagemath.org/ticket/9944#comment:87
https://trac.sagemath.org/ticket/9944#comment:87
<p>
I couldn't replace the patches so the rebased versions have new names. I will attach a diff file in a second (only line numbers changed).
</p>
<p>
Everything looks good to me now. I just want to run all tests one more time and then this can get a positive review.
</p>
TicketmraumThu, 19 May 2011 12:48:11 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>coerce.diff</em>
</li>
</ul>
TicketmraumThu, 19 May 2011 12:48:18 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>speedup.diff</em>
</li>
</ul>
TicketmraumThu, 19 May 2011 12:49:45 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:88
https://trac.sagemath.org/ticket/9944#comment:88
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=88">diff</a>)
</li>
</ul>
<p>
Updating the apply statements.
</p>
TicketSimonKingThu, 19 May 2011 13:19:27 GMT
https://trac.sagemath.org/ticket/9944#comment:89
https://trac.sagemath.org/ticket/9944#comment:89
<p>
Hi Martin,
</p>
<p>
could it be that you had worked with an old version of <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Attachment 'trac9944_polynomial_speedup.patch' in Ticket #9944">trac9944_polynomial_speedup.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_polynomial_speedup.patch" title="Download"></a>?
</p>
<p>
There was a misspelling that I had introduced into the documentation of polynomial base injection maps, in the original version of that patch: It was
</p>
<pre class="wiki">We use `_rmul_` and not `_lmul_` since...
</pre><p>
where it should have been
</p>
<pre class="wiki">We use ``_rmul_`` and not ``_lmul_`` since...
</pre><p>
I had corrected that typo and updated the patch. But in your version <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac-9944-polynomial_speedup.patch" title="Attachment 'trac-9944-polynomial_speedup.patch' in Ticket #9944">trac-9944-polynomial_speedup.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac-9944-polynomial_speedup.patch" title="Download"></a>, you still have the single back tick.
</p>
<p>
Anyway. If you apply my version or your version of the two patches, the result will be the same, namely two backticks around _rmul_ and _lmul_
</p>
TicketSimonKingThu, 19 May 2011 13:51:24 GMT
https://trac.sagemath.org/ticket/9944#comment:90
https://trac.sagemath.org/ticket/9944#comment:90
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:89" title="Comment 89">SimonKing</a>:
</p>
<blockquote class="citation">
<p>
Anyway. If you apply my version or your version of the two patches, the result will be the same, namely two backticks around _rmul_ and _lmul_
</p>
</blockquote>
<p>
Or rather: The result will be in both cases that that text line will be completely removed.
</p>
TicketmraumThu, 19 May 2011 13:55:21 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:91
https://trac.sagemath.org/ticket/9944#comment:91
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Ok, all tests still pass.
</p>
TicketSimonKingSun, 22 May 2011 18:25:14 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:92
https://trac.sagemath.org/ticket/9944#comment:92
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=92">diff</a>)
</li>
</ul>
<p>
By now, all patches have a positive review, so, I am changing the distinction of patches with or without positive review in the list of to-be-applied patches in the ticket description.
</p>
TicketSimonKingSun, 22 May 2011 18:26:23 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:93
https://trac.sagemath.org/ticket/9944#comment:93
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=93">diff</a>)
</li>
</ul>
TicketSimonKingMon, 23 May 2011 18:46:19 GMTstatus, description changed
https://trac.sagemath.org/ticket/9944#comment:94
https://trac.sagemath.org/ticket/9944#comment:94
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=94">diff</a>)
</li>
</ul>
<p>
I hope it is OK that I modified one test in sage.rings.polynomial.polynomial_ring, by the new patch <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_addendum.patch" title="Attachment 'trac9944_addendum.patch' in Ticket #9944">trac9944_addendum.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_addendum.patch" title="Download"></a>.
</p>
<p>
That test used to be
</p>
<pre class="wiki">sage: QQ['y'] < QQ['x']
False
sage: QQ['y'] < QQ['z']
True
</pre><p>
But that is unsafe, because this ticket removes the custom <code>__cmp__</code> method of polynomial rings. So, the comparison relies on virtually random data such as <code>id(QQ['x'])</code>, if I am not mistaken.
</p>
<p>
Therefore, it seems safer to me to replace it by
</p>
<pre class="wiki">sage: QQ['y'] != QQ['x']
True
sage: QQ['y'] != QQ['z']
True
</pre>
TicketSimonKingMon, 23 May 2011 18:46:40 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:95
https://trac.sagemath.org/ticket/9944#comment:95
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketmraumMon, 23 May 2011 20:00:18 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:96
https://trac.sagemath.org/ticket/9944#comment:96
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I'm not sure how happy the release manager is with changing tickets after positive review (except it is him who is doing it).
But I completely agree that this change makes sense. As expected, all tests pass, so I can change this back to positive review.
</p>
TicketSimonKingMon, 23 May 2011 21:02:49 GMT
https://trac.sagemath.org/ticket/9944#comment:97
https://trac.sagemath.org/ticket/9944#comment:97
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/9944#comment:96" title="Comment 96">mraum</a>:
</p>
<blockquote class="citation">
<p>
I'm not sure how happy the release manager is with changing tickets after positive review (except it is him who is doing it).
</p>
</blockquote>
<p>
I reckon that it does not matter to the release manager, unless one re-opens a ticket that is already closed (but that has not been the case here).
</p>
<blockquote class="citation">
<p>
But I completely agree that this change makes sense. As expected, all tests pass, so I can change this back to positive review.
</p>
</blockquote>
<p>
Thank you!
</p>
TicketSimonKingTue, 24 May 2011 06:55:34 GMTdescription changed
https://trac.sagemath.org/ticket/9944#comment:98
https://trac.sagemath.org/ticket/9944#comment:98
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/9944?action=diff&version=98">diff</a>)
</li>
</ul>
<p>
I removed the comment "needs review" from the ticket description.
</p>
TicketjdemeyerTue, 24 May 2011 12:51:49 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:99
https://trac.sagemath.org/ticket/9944#comment:99
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
One minor issue: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/9944/trac9944_addendum.patch" title="Attachment 'trac9944_addendum.patch' in Ticket #9944">trac9944_addendum.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/9944/trac9944_addendum.patch" title="Download"></a> needs a proper commit message.
</p>
TicketSimonKingTue, 24 May 2011 13:51:46 GMTattachment set
https://trac.sagemath.org/ticket/9944
https://trac.sagemath.org/ticket/9944
<ul>
<li><strong>attachment</strong>
set to <em>trac9944_addendum.patch</em>
</li>
</ul>
<p>
Making one doctest safer
</p>
TicketSimonKingTue, 24 May 2011 13:52:18 GMTstatus changed
https://trac.sagemath.org/ticket/9944#comment:100
https://trac.sagemath.org/ticket/9944#comment:100
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
</ul>
<p>
Done!
</p>
TicketjdemeyerTue, 31 May 2011 09:50:01 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/9944#comment:101
https://trac.sagemath.org/ticket/9944#comment:101
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.7.1.alpha2</em>
</li>
</ul>
TicketleifMon, 12 Sep 2011 13:00:01 GMTdependencies changed
https://trac.sagemath.org/ticket/9944#comment:102
https://trac.sagemath.org/ticket/9944#comment:102
<ul>
<li><strong>dependencies</strong>
changed from <em>sage-4.7 + #11139</em> to <em>#11139</em>
</li>
</ul>
Ticket