#11943: The category graph should comply with Python's method resolution order
---------------------------+------------------------------------------------
Reporter: SimonKing | Owner: nthiery
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.8
Component: categories | Keywords: category graph, method resolution
order
Work_issues: | Upstream: N/A
Reviewer: | Author: Simon King
Merged: | Dependencies: #11900
---------------------------+------------------------------------------------
Comment(by SimonKing):
Replying to [comment:22 SimonKing]:
> I am afraid I can not show you the original example that made me suggest
this bit of code.
Now I remember the story.
By #9138, we have that the category of a polynomial ring is the join of a
category of algebras with a base-free algebra, for example:
{{{
sage: P.<x,y> = ZZ[]
sage: P.category()
Join of Category of unique factorization domains and Category of
commutative algebras over Integer Ring
}}}
Originally, that category has been computed via
{{{
sage: Category.join([UniqueFactorizationDomains(),
CommutativeAlgebras(ZZ)])
Join of Category of unique factorization domains and Category of
commutative algebras over Integer Ring
}}}
But that turned out to be a problem for elliptic curve computations:
* In the benchmarks discussed on #11900, polynomial rings over many
different finite fields are constructed.
* For each of them, `Category.join(...)` was called.
* Internally, `Category.join(...)` tests whether the categories to be
joined are sub-categories of each other.
* Hence, for each prime p, one had to compute
`CommutativeAlgebras(GF(p)).all_super_categories()`, in order to test
whether it is a sub-category of `UniqueFactorizationDomains()`.
In fact, that was the main reason for the speed regression from #9138.
For fixing it, I had (at least) the following two ideas:
1. Do not call `Category.join(...)`, but construct `JoinCategory(...)`
directly. Advantage: `JoinCategory.__init__` does not test for sub-
categories. So, no time is wasted.
1. When testing
`UniqueFactorizationDomains().is_subcategory(CommutativeAlgebras(F))`, one
does not need to waste time by computing
`CommutativeAlgebras(F).all_super_categories()`. The fact that
`UniqueFactorizationDomains()` has no base ring suffices to recognise
that it is not a sub-category.
In #11900, I went for the first approach. Here, I'd like to also add the
second approach. It is not needed for fixing an existing regression, but I
still think it is a good idea.
Here is an example for what I have explained:
We start with a list of categories of algebras over different finite
fields. The aim is to compute the join with the category of unique
factorization domains.
{{{
sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()
}}}
With sage-4.6.2 (as an old reference):
{{{
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.65 s, sys: 0.00 s, total: 0.65 s
Wall time: 0.65 s
}}}
With sage-4.7.2.alpha3 (hence, with #9138, but without #11900):
{{{
sage: L = [CommutativeAlgebras(GF(p)) for p in prime_range(5000)]
sage: C = UniqueFactorizationDomains()
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.76 s, sys: 0.00 s, total: 0.77 s
Wall time: 0.77 s
}}}
With unpatched sage-4.7.3.alpha1 (which contains #11900):
{{{
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.59 s, sys: 0.01 s, total: 0.60 s
Wall time: 0.61 s
}}}
With sage-4.7.3.alpha1 plus the patch from here (thus, using base rings):
{{{
sage: %time X = [Category.join([C,A]) for A in L]
CPU times: user 0.39 s, sys: 0.00 s, total: 0.39 s
Wall time: 0.39 s
}}}
Believe it or not, but that kind of differences had a noticeable effect,
as I found out while working on #11900.
'''__Conclusion__'''
I still believe that one should exploit the base of a category for short-
cuts in subcategory tests.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11943#comment:23>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
