Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Categories for all rings #9138

Closed
jbandlow opened this issue Jun 4, 2010 · 165 comments
Closed

Categories for all rings #9138

jbandlow opened this issue Jun 4, 2010 · 165 comments

Comments

@jbandlow
Copy link

jbandlow commented Jun 4, 2010

Introspection is failing on polynomial rings:

sage: R.<x> = QQ[] 
sage: R.su<tab> 
R.sum                               R.summation 
R.summation_from_element_class_add 
sage: R.sum? 
Object `R.sum` not found. 
sage: R.sum() 
--------------------------------------------------------------------------- 
AttributeError                            Traceback (most recent call last) 

This is because polynomial rings do not yet set their category properly:

sage: QQ[x]._test_category()
------------------------------------------------------------
Traceback (most recent call last):
...
AssertionError: category of self improperly initialized

See http://groups.google.com/group/sage-devel/browse_thread/thread/4780192a11a8b591 for more discussion.

Many other rings are not properly initialised as well. The aim of this ticket is to change that.

Apply attachment: 9138_flat.patch (rebased on top of #9958, but will still apply with fuzz 2 otherwise).

See #11900 for a follow-up fixing some speed regressions.

Depends on #11900

Dependencies: To be merged with #11900

CC: @sagetrac-sage-combinat @robertwb

Component: categories

Keywords: introspection, categories for rings

Author: Simon King

Reviewer: Volker Braun

Merged: sage-5.0.beta0

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

@nthiery

This comment has been minimized.

@nthiery nthiery changed the title Introspection is failing on polynomial rings Categories for polynomial rings Jun 5, 2010
@mezzarobba
Copy link
Member

comment:2

This ticket seems to be a duplicate of #8613.

@nthiery
Copy link
Contributor

nthiery commented Jun 7, 2010

comment:3

Replying to @mezzarobba:

This ticket seems to be a duplicate of #8613.

Indeed. This should have ringed a bell to me!

Since I have already recycled this ticket to "Categories for
polynomial ring", I leave the two tickets as is. Once this ticket will
be closed, it should be possible to close #8613 as well.

@simon-king-jena
Copy link
Member

comment:4

This ticket is just about a single kind of parent classes. Rather than going through a long list of parent classes one by one and inserting the missing pieces: Wouldn't it be a more thorough approach to provide a default implementation for the attributes needed in the category framework, in cases where it makes sense?

Here is an example:

sage: R.<x,y> = QQ[]
sage: 'element_class' in dir(R)
True
sage: hasattr(R,'element_class')
False

If I am not mistaken, "element_class" should be implemented by providing the attribute "Element".

But is there a reason why element_class is a dynamic meta-class and not a regular method? Since any parent class has a "an_element" method, it seems to me that the following default implementation makes sense (and it solves the problem in my example above):

    def element_class(self):
        try:
            return self.Element
        except AttributeError:
            return self.an_element().__class__

It seems to me that providing reasonable default implementations would, on the long run, be easier than going through any single parent class. But certainly other people know more about the "how-to" of categories.

@simon-king-jena
Copy link
Member

comment:5

Replying to @simon-king-jena:

But is there a reason why element_class is a dynamic meta-class and not a regular method?

Sorry, I just noticed that "element_class" is not a method at all: I assumed that it should be used like R.element_class(), but sadly it is R.element_class without calling the attribute. So, one attribute (element_class) is implemented by providing another attribute (Element).

Anyway, if there shall be a default implementation for element_class then unfortunately it must be in __getattr__.

@simon-king-jena
Copy link
Member

comment:6

Replying to @simon-king-jena:

Replying to @simon-king-jena:

But is there a reason why element_class is a dynamic meta-class and not a regular method?

Sorry, I just noticed that "element_class" is not a method at all...

Again wrong. I found in sage.structure.parent that there is indeed a method element_class -- with a lazy_attribute decorator. I am still confused by that programming style, so, better I shut up.

Anyway, changing the element_class method so that an_element is used (rather than raising an AttributeError) did not help. Can you explain why this does not work?

@simon-king-jena
Copy link
Member

comment:7

Question: Is it OK to broaden the scope of this ticket, namely to use the category framework for everything that comes from sage/rings/ring.pyx? Or shall it be restricted to polynomial rings.

@simon-king-jena
Copy link
Member

Author: Simon King

@simon-king-jena
Copy link
Member

comment:8

Since #9944 almost has a positive review but does not entirely fix the bug reported here, I'm posting my patch here, building on top of that.

Examples:

With the patches from #9944:

sage: QQ['x'].category()        # why not additionally an algebra?
Category of euclidean domains
sage: QQ['x','y'].category()    # why not an algebra?
Category of commutative rings
sage: SteenrodAlgebra(2)['x'].category()  # this is wrong
Category of commutative rings
sage: QQ['x','y'].sum([1,1])
Traceback (most recent call last):
...
AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomialRing_libsingular' object has no attribute 'sum'

Adding my (not yet submitted) patch, I get:

sage: QQ['x'].category()
Join of Category of euclidean domains and Category of commutative algebras over Rational Field
sage: QQ['x','y'].category()
Category of commutative algebras over Rational Field
sage: SteenrodAlgebra(2)['x'].category()
Category of algebras over mod 2 Steenrod algebra
sage: QQ['x','y'].sum([1,1])
2

So, I think the bug reported here is fixed. For me, all doctests pass.

Depends on #9944

@simon-king-jena
Copy link
Member

comment:9

Replying to @simon-king-jena:

Adding my (not yet submitted) patch, ...

Oops, I meant: That's with the patch that I have submitted...

@jbandlow
Copy link
Author

comment:10

Hi Simon,

I haven't been following all the details of this, but thanks for the patch! One question I have is whether there is a performance penalty for this, and if so, to what degree is that acceptable. On my machine, I noticed about a 10% slow-down for

    sage: R.<x> = QQ['x']
    sage: timeit('f = x^2 + 1')

after applying the patches at #9944 and here. I did not do any rigorous testing so this may be spurious, but I'm not sure this should be given a positive review unless this issue has at least been considered.

If this has already happened and I missed the discussion, then I apologize. Just point me to it and I'll shut up and go away. :)

@simon-king-jena
Copy link
Member

comment:11

Hi Jason,

Replying to @jbandlow:

I did not do any rigorous testing so this may be spurious, but I'm not sure this should be given a positive review unless this issue has at least been considered.

You are right, things like this should be considered. However, I wonder where a slow-down might come from.

If this has already happened and I missed the discussion, then I apologize. Just point me to it and I'll shut up and go away. :)

No, I wasn't testing the performance. Aparently I work in cycles: Recently I had several patches that considerably increased performance, and perhaps I am now in a slow mood again...

Anyway, I'll do some tests now.

@simon-king-jena
Copy link
Member

comment:12

Here are the test results:

Without all patches:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 22.5 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 24.5 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 87.7 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 114 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 21.9 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 40 µs per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 26.3 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 239 µs per loop

With the patches from #9944:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 25.6 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 26.7 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 109 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 121 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 31.4 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 40 µs per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 26.8 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 250 µs per loop

With the patches from #9944 and the patch from here:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 25.7 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 28.3 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 115 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 125 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 31 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 17.5 µs per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 25.1 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 256 µs per loop

Note, however, that the numbers arent't very stable

sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 20.9 µs per loop
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 20.8 µs per loop
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 22.6 µs per loop
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 37.9 µs per loop
sage: timeit('(2*x-1)^2+5')
625 loops, best of 3: 15.4 µs per loop

But there is a tendency: Things tend to be slower, both with #9944 and with my patch.

So, it should be worth while to analyse the arithmetic with prun.

@simon-king-jena
Copy link
Member

comment:13

By the way, I think we should add doctests of the type

sage: TestSuite(QQ['x']).run()
sage: TestSuite(QQ['x','y']).run()
sage: TestSuite(QQ['x','y']['t']).run()
sage: TestSuite(GF(3)['t']).run()
sage: TestSuite(ZZ['t']).run()

If I understand the ticket description, this used to fail.

@simon-king-jena
Copy link
Member

comment:14

Idea: Could it be that the length of the method resolution order is responsible for the slow-down?

With all patches:

sage: len(type(QQ['x']).mro())
47
sage: len(type(QQ['x','y']).mro())
11
sage: len(type(GF(3)['x','y']).mro())
11
sage: len(type(GF(3)['x']).mro())
49
sage: len(type(ZZ['x']).mro())
41
sage: len(type(ZZ['x']['t']).mro())
41
sage: len(type(QQ['x'].gen()).mro())
9
sage: len(type(QQ['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x'].gen()).mro())
10
sage: len(type(ZZ['x'].gen()).mro())
9
sage: len(type(ZZ['x']['t'].gen()).mro())
9

With only the patches from #9944:

sage: len(type(QQ['x']).mro())
39
sage: len(type(QQ['x','y']).mro())
11
sage: len(type(GF(3)['x','y']).mro())
11
sage: len(type(GF(3)['x']).mro())
41
sage: len(type(ZZ['x']).mro())
34
sage: len(type(ZZ['x']['t']).mro())
34
sage: len(type(QQ['x'].gen()).mro())
9
sage: len(type(QQ['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x'].gen()).mro())
10
sage: len(type(ZZ['x'].gen()).mro())
9
sage: len(type(ZZ['x']['t'].gen()).mro())
9

Without these patches:

sage: len(type(QQ['x']).mro())
18
sage: len(type(QQ['x','y']).mro())
11
sage: len(type(GF(3)['x','y']).mro())
11
sage: len(type(GF(3)['x']).mro())
20
sage: len(type(ZZ['x']).mro())
15
sage: len(type(ZZ['x']['t']).mro())
15
sage: len(type(QQ['x'].gen()).mro())
9
sage: len(type(QQ['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x','y'].gen()).mro())
8
sage: len(type(GF(3)['x'].gen()).mro())
10
sage: len(type(ZZ['x'].gen()).mro())
9
sage: len(type(ZZ['x']['t'].gen()).mro())
9

So, the mro of the rings becomes much longer. Could it be that, as a consequence, it takes longer to find common and frequently used methods such as R.parent() and R.base_ring()?

@simon-king-jena
Copy link
Member

comment:15

Here are times for basic methods (i.e., methods that require to walk up much of the mro):

Without patches

sage: R.<x> = ZZ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 253 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 447 ns per loop
sage: R.<x> = QQ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 249 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 508 ns per loop
sage: R.<x> = GF(3)[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 262 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 555 ns per loop
sage: R.<x> = QQ['t'][]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 249 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 446 ns per loop
sage: R.<x,y> = ZZ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 240 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 286 ns per loop
sage: R.<x,y> = QQ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 240 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 282 ns per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 245 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 284 ns per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 266 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 413 ns per loop

With all patches

sage: R.<x> = ZZ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 539 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 476 ns per loop
sage: R.<x> = QQ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 247 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 652 ns per loop
sage: R.<x> = GF(3)[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 670 ns per loop
sage: timeit('R.base_ring()',number=10^5)
sage: R.<x> = QQ['t'][]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 254 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 496 ns per loop
sage: R.<x,y> = ZZ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 583 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 297 ns per loop
sage: R.<x,y> = QQ[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 237 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 307 ns per loop
sage: R.<x,y> = GF(3)[]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 237 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 294 ns per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('x.parent()',number=10^5)
100000 loops, best of 3: 277 ns per loop
sage: timeit('R.base_ring()',number=10^5)
100000 loops, best of 3: 477 ns per loop

So, there seems to be some slow-down in accessing basic methods.

@simon-king-jena
Copy link
Member

comment:16

But apparently one can work around the mro:

sage: timeit('R.base_ring()',number=10^6)
1000000 loops, best of 3: 470 ns per loop
sage: timeit('Parent.base_ring(R)',number=10^6)
1000000 loops, best of 3: 352 ns per loop

So, if speed matters, it might be worth while to use the idiom above to speed things up. I'll ask on sage-devel whether there is a more elegant/pythonic way to cope with a long mro.

@simon-king-jena
Copy link
Member

comment:17

I had to rebase my patch since it

Depends on #9944

@simon-king-jena
Copy link
Member

comment:18

With the latest patches, I obtain the following timings:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 25.8 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 27.8 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 112 µs per loop
sage: R.<x> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 124 µs per loop
sage: R.<x,y> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 12.7 µs per loop
sage: R.<x,y> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 15.7 µ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.3 µs per loop
sage: R.<x,y> = QQ['t'][]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 148 µs per loop

Without these patches:

sage: R.<x> = ZZ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 22.7 µs per loop
sage: R.<x> = QQ[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 24.2 µs per loop
sage: R.<x> = GF(3)[]
sage: timeit('(2*x-1)^2+5', number=10^4)
10000 loops, best of 3: 87 µ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.3 µ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: 237 µs per loop

In other words, there is a mild deceleration in the univariate case and a mild (and in one case considerable) acceleration in the multivariate case.

I don't understand why. But perhaps a reviewer has an idea, and can also state his or her opinion how bad the deceleration is compared with the acceleration?

@simon-king-jena
Copy link
Member

comment:123

A note to the release manager: #11900 just got a positive review by Nicolas Thiéry.

@jdemeyer jdemeyer added this to the sage-5.0 milestone Dec 9, 2011
@jdemeyer jdemeyer removed the pending label Dec 9, 2011
@jdemeyer
Copy link

jdemeyer commented Jan 5, 2012

Attachment: 9138_flat.patch.gz

All patches together in one patch, rebased to #9958

@jdemeyer

This comment has been minimized.

@jdemeyer
Copy link

Merged: sage-5.0.beta0

@burcin burcin mentioned this issue Jan 21, 2012
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

9 participants