categories for polynomial rings

[robertwb]

Currently, they're always just commutative rings.

Apply:

1. attachment: 9944-poly-cat.patch
2. attachment: trac-9944-poly_cat_doctests.patch
3. attachment: trac-9944-poly-cat-review.patch
4. attachment: trac-9944-polynomial_speedup.patch
5. attachment: trac9944_abvar_endomorphism.patch
6. attachment: trac9944_faster_and_cleaner_coercion.2.patch
7. attachment: trac9944_addendum.patch

Note

The same result can be obtained with the original patches:

1. attachment: 9944-poly-cat.patch
2. attachment: trac-9944-poly_cat_doctests.patch
3. attachment: trac-9944-poly-cat-review.patch
4. attachment: trac9944_polynomial_speedup.patch (Note the name difference to 4. above)
5. attachment: trac9944_abvar_endomorphism.patch
6. attachment: trac9944_faster_and_cleaner_coercion.patch (Note the name difference to 6. above)
7. attachment: trac9944_addendum.patch

Depends on #11139

CC: @sagetrac-sage-combinat

Component: categories

Author: Robert Bradshaw, Simon King

Reviewer: Nicolas M. Thiéry, Mike Hansen, Martin Raum

Merged: sage-4.7.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/9944

[robertwb]

comment:1

Attachment: 9944-poly-cat.patch.gz

[nthiery]

comment:2

Hi Robert!

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!

Just one micro question: does PolynomialRing actually check that the ring is commutative?

Cheers

[mwhansen]

Author: Robert Bradshaw

[mwhansen]

Reviewer: Nicolas M. Thiéry, Mike Hansen

[mwhansen]

comment:3

Attachment: trac_9944.patch.gz

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?

[robertwb]

comment:4

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?).

I don't know if PolynomialRing asserts its basering is commutative, but IIRC it's been assumed for a long time.

[robertwb]

comment:5

Apply only 9944-poly-cat.patch

[robertwb]

Attachment: 9944-poly-cat-doctests.patch.gz

[robertwb]

comment:6

Apply 9944-poly-cat.patch and 9944-poly-cat-doctests.patch .

[sagetrac-mraum]

comment:7

Attachment: trac-9944-poly-cat-review.patch.gz

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.

[nthiery]

comment:8

Replying to @robertwb:

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?).

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.

And yes, we have join categories. See Category.join.

I let you see whether to create the UnivariatePolynomialRing category
in this ticket or in a later ticket.

[simon-king-jena]

comment:9

Replying to @nthiery:

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.

Aparently there is a doctest failure. I fixed it, but unfortunately it went into my patch submitted for #9138. Therefore, "needs work".

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 #9138) 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.

My suggestion is that I submit a small patch fixing the doctests. Please tell whether my patch for #9138 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 #9138.

[simon-king-jena]

Work Issues: Fix one test

[simon-king-jena]

comment:11

At #9138, 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?

[simon-king-jena]

comment:12

Replying to @simon-king-jena:

Aparently there is a doctest failure. I fixed it, but unfortunately it went into my patch submitted for #9138. Therefore, "needs work".

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 #9138, because it turns QQ['x'].category() into the join of the category of euclidean domains and commutative algebras over QQ.

The other issue, namely the performance loss, was studied on sage-devel.

Florent Hivert found that a long mro does not matter for Python, but it does matter if the classes inherit from a cdef class. That is the case for most classes in Sage (inheriting from SageObject), so, we should address the problem of a long mro.

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.

Would it be acceptable coding practice to explicitly state in a derived class (say, MPolynomialRing_generic), that frequently used methods such as base or base_ring are the same as Parent.base or Parent.base_ring? David Roe stated that it might be dangerous to do so, at least if cpdef methods are involved.

[simon-king-jena]

comment:13

Concerning performance loss:

It seems to me that part of the reason is the fact that with the patchse, __init_extra__ is not executed when it should. Sometimes, the parent methods of a category provide a useful __init_extra__, for example the category of algebras.

I am not sure yet why that happens, but I think it would happen if Parent.__init__ is called without providing the category: Namely, doing self._init_category_(...) alone will not trigger the execution of __init_extra__.

[simon-king-jena]

comment:14

It seems I was right!

Namely, the whole ring stuff is (unfortunately) inherited from ParentWithGens, which inherits from ParentWithBase, which inherits from parent_old.Parent.

And parent_old.Parent inherits from "the one and only Parent" -- but forgets to call Parent.__init__!! Instead, it just does self._init_category_(...).

I'll change it and see what happens.

[simon-king-jena]

comment:15

Very bad things happen. As soon as parent.Parent.__init__ is called in parent_old.Parent.__init__, an infinite recursion occurs.

[simon-king-jena]

Call Parent.init during initialisation of a ring

[simon-king-jena]

comment:94

I hope it is OK that I modified one test in sage.rings.polynomial.polynomial_ring, by the new patch attachment: trac9944_addendum.patch.

That test used to be

sage: QQ['y'] < QQ['x']
False
sage: QQ['y'] < QQ['z']
True

But that is unsafe, because this ticket removes the custom __cmp__ method of polynomial rings. So, the comparison relies on virtually random data such as id(QQ['x']), if I am not mistaken.

Therefore, it seems safer to me to replace it by

sage: QQ['y'] != QQ['x']
True
sage: QQ['y'] != QQ['z']
True

[sagetrac-mraum]

comment:96

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.

[simon-king-jena]

comment:97

Replying to @sagetrac-mraum:

I'm not sure how happy the release manager is with changing tickets after positive review (except it is him who is doing it).

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).

But I completely agree that this change makes sense. As expected, all tests pass, so I can change this back to positive review.

Thank you!

[simon-king-jena]

comment:98

I removed the comment "needs review" from the ticket description.

[jdemeyer]

comment:99

One minor issue: attachment: trac9944_addendum.patch needs a proper commit message.

[simon-king-jena]

Attachment: trac9944_addendum.patch.gz

Making one doctest safer

[simon-king-jena]

comment:100

Done!

[jdemeyer]

Merged: sage-4.7.1.alpha2

[nexttime]

Changed dependencies from sage-4.7 + #11139 to #11139