Opened 13 years ago
Closed 12 years ago
#8807 closed enhancement (fixed)
Adding support for morphisms to the category framework
Reported by: | Simon King | Owned by: | Simon King |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.2 |
Component: | categories | Keywords: | morphisms functors categories |
Cc: | David Kohel, William Stein, David Joyner, Robert Bradshaw | Merged in: | sage-4.6.2.alpha0 |
Authors: | Simon King | Reviewers: | John Cremona |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Working on the doc tests for sage.category at #8800, I found that support for morphisms is missing in the category framework. I think this is important, and therefore I am opening this ticket.
Some thoughts on implementing support.
Let f be a morphism in a category C, and let F be a functor, F.domain()==C. Then F(f) should by default try F(f.domain()).hom(f,F(f.codomain())). This relies on the call method of F(f.domain()).Hom(F.codomain()), which in turn uses _coerce_impl. I think it is there where the support should be implemented.
Example:
In sage.rings.homset.RingHomset_generic_with_category._coerce_impl, one has
... if x.parent() == self: if isinstance(x, morphism.RingHomomorphism_im_gens): return morphism.RingHomomorphism_im_gens(self, x.im_gens()) elif isinstance(x, morphism.RingHomomorphism_cover): return morphism.RingHomomorphism_cover(self) raise TypeError
Why not instead
try: if isinstance(x, morphism.RingHomomorphism_im_gens): return morphism.RingHomomorphism_im_gens(self, x.im_gens()) elif isinstance(x, morphism.RingHomomorphism_cover): return morphism.RingHomomorphism_cover(self) except: raise TypeError
If I do so, the following works:
sage: R.<x> = QQ[] sage: f = R.hom([2*x],R) sage: C = Fields() sage: f2 = C(R).hom(f,C(R)) sage: f2 Ring endomorphism of Fraction Field of Univariate Polynomial Ring in x over Rational Field Defn: x |--> 2*x sage: f2(1/x) 1/(2*x)
It should be straight forward to change the call method of C
so that
C(f)
reproduces the above construction. Similarly, if
F
is a functor then
F(f)
should call
F(f.domain()).hom(f,F(f.codomain()))
.
Attachments (3)
Change History (25)
Changed 13 years ago by
Attachment: | 8807functors_and_induced_morphisms.patch added |
---|
Changed 13 years ago by
Attachment: | 8807functors_and_induced_morphisms.p1.patch added |
---|
Fixing a buglet in the construction functor of Laurent Polynomial Rings. To be applied after the first patch
comment:1 Changed 13 years ago by
Cc: | David Kohel William Stein David Joyner Robert Bradshaw added |
---|---|
Status: | new → needs_review |
Cc to the original authors.
I solved the problem. Please apply both patches in order.
New Code
I cleaned the framework for functors. There is a generic call method that (in contrast to the old generic call method) has a return value. It relies on three methods _coerce_into_domain, _apply_functor and _apply_functor_to_morphism. The default methods are already enough for forgetful functor and most construction functors.
I implemented a new class for Ring Homomorphisms that are induced by a homomorphism of the base ring. This enables the application of the construction functors for matrix and polynomial rings.
Tests
All new code is tested, and I added also some doc tests for old code. This is related with #8800. However, #8800 should not be closed, because the old code is still not completely covered by tests yet.
Suggestion: The further work on #8800 will build upon this ticket.
Showcases
We start with a homomorphism of polynomial rings.
sage: R.<x,y> = QQ[] sage: S.<z> = QQ[] sage: f = R.hom([2*z,3*z],S)
Now we construct polynomial rings based on R
and
S
, and let
f
act on the coefficients:
sage: PR.<t> = R[] sage: PS = S['t'] sage: Pf = PR.hom(f,PS) sage: Pf Ring morphism: From: Univariate Polynomial Ring in t over Multivariate Polynomial Ring in x, y over Rational Field To: Univariate Polynomial Ring in t over Univariate Polynomial Ring in z over Rational Field Defn: Induced from base ring by Ring morphism: From: Multivariate Polynomial Ring in x, y over Rational Field To: Univariate Polynomial Ring in z over Rational Field Defn: x |--> 2*z y |--> 3*z sage: p = (x - 4*y + 1/13)*t^2 + (1/2*x^2 - 1/3*y^2)*t + 2*y^2 + x sage: Pf(p) (-10*z + 1/13)*t^2 - z^2*t + 18*z^2 + 2*z
The construction of induced homomorphisms is recursive, and so we have:
sage: MPR = MatrixSpace(PR, 2) sage: MPS = MatrixSpace(PS, 2) sage: M = MPR([(- x + y)*t^2 + 58*t - 3*x^2 + x*y, (- 1/7*x*y - 1/40*x)*t^2 + (5*x^2 + y^2)*t + 2*y, (- 1/3*y + 1)*t^2 + 1/3*x*y + y^2 + 5/2*y + 1/4, (x + 6*y + 1)*t^2]) sage: MPf = MPR.hom(f,MPS); MPf Ring morphism: From: Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in t over Multivariate Polynomial Ring in x, y over Rational Field To: Full MatrixSpace of 2 by 2 dense matrices over Univariate Polynomial Ring in t over Univariate Polynomial Ring in z over Rational Field Defn: Induced from base ring by Ring morphism: From: Univariate Polynomial Ring in t over Multivariate Polynomial Ring in x, y over Rational Field To: Univariate Polynomial Ring in t over Univariate Polynomial Ring in z over Rational Field Defn: Induced from base ring by Ring morphism: From: Multivariate Polynomial Ring in x, y over Rational Field To: Univariate Polynomial Ring in z over Rational Field Defn: x |--> 2*z y |--> 3*z sage: MPf(M) [ z*t^2 + 58*t - 6*z^2 (-6/7*z^2 - 1/20*z)*t^2 + 29*z^2*t + 6*z] [ (-z + 1)*t^2 + 11*z^2 + 15/2*z + 1/4 (20*z + 1)*t^2]
And this can also be achieved using construction functors:
sage: from sage.categories.pushout import CompositConstructionFunctor sage: F = CompositConstructionFunctor(QQ.construction()[0],ZZ['x'].construction()[0], QQ.construction()[0],ZZ['y'].construction()[0]) sage: R.<a,b> = QQ[] sage: f = R.hom([a+b, a-b]) sage: F(f) # indirect doctest Ring endomorphism of Univariate Polynomial Ring in y over Fraction Field of Univariate Polynomial Ring in x over Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field Defn: Induced from base ring by Ring endomorphism of Fraction Field of Univariate Polynomial Ring in x over Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field Defn: Induced from base ring by Ring endomorphism of Univariate Polynomial Ring in x over Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field Defn: Induced from base ring by Ring endomorphism of Fraction Field of Multivariate Polynomial Ring in a, b over Rational Field Defn: a |--> a + b b |--> a - b
With the second patch, Laurent polynomial rings work as well:
sage: P = LaurentPolynomialRing(QQ,'t') sage: F = P.construction()[0] sage: X.<t> = LaurentPolynomialRing(R) sage: p = (a+b)*t^-1 + (a^2)*t + b sage: F(f)(p) (a^2 + 2*a*b + b^2)*t + a - b + 2*a*t^-1
comment:2 follow-up: 3 Changed 12 years ago by
Status: | needs_review → needs_work |
---|
I applied this patch to sage-4.5, and ran "make ptestlong", and their are failures all over the place, e.g.,
wstein@sage:~/build/sage-4.5.alphastein1$ ./sage -t -long devel/sage/sage/matrix/misc.pyx sage -t -long "devel/sage/sage/matrix/misc.pyx" ********************************************************************** File "/mnt/usb1/scratch/wstein/build/sage-4.5.alphastein1/devel/sage/sage/matrix/misc.pyx", line 67: sage: B = ((matrix(ZZ, 3,4, [1,2,3,-4,7,2,18,3,4,3,4,5])/3)%500).change_ring(ZZ) Exception raised: Traceback (most recent call last): File "/mnt/usb1/scratch/wstein/build/sage-4.5.alphastein1/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/mnt/usb1/scratch/wstein/build/sage-4.5.alphastein1/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/mnt/usb1/scratch/wstein/build/sage-4.5.alphastein1/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_1[2]>", line 1, in <module> B = ((matrix(ZZ, Integer(3),Integer(4), [Integer(1),Integer(2),Integer(3),-Integer(4),Integer(7),Integer(2),Integer(18),Integer(3),Inte ger(4),Integer(3),Integer(4),Integer(5)])/Integer(3))%Integer(500)).change_ring(ZZ)###line 67: sage: B = ((matrix(ZZ, 3,4, [1,2,3,-4,7,2,18,3,4,3,4,5])/3)%500).change_ring(ZZ) File "element.pyx", line 1529, in sage.structure.element.RingElement.__div__ (sage/structure/element.c:11992) File "coerce.pyx", line 765, in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6966) TypeError: unsupported operand parent(s) for '/': 'Full MatrixSpace of 3 by 4 dense matrices over Integer Ring' and 'Integer Ring' ...
comment:3 Changed 12 years ago by
Dear William,
thanks for looking at this! Indeed it has been a long time since I wrote it, so it is time to resume work, taking a fresh look at my own code. I think this will be my project for the rest of Sage Days 24!
comment:4 Changed 12 years ago by
It seems that my patch crashed the coercion system. Funny coincidence that I held a tutorial on coercion today...
sage: cm = get_coercion_model() sage: M = parent(matrix(ZZ, 3,4, [1,2,3,-4,7,2,18,3,4,3,4,5])) sage: cm.explain(M,QQ) Will try _r_action and _l_action Unknown result parent.
Cheers, Simon
comment:5 Changed 12 years ago by
And there it is:
sage: M = parent(matrix(ZZ, 3,4, [1,2,3,-4,7,2,18,3,4,3,4,5])) sage: mf = M.construction()[0] sage: mf.domain() Category of rings sage: mf.codomain() Category of rings sage: M in Rings() False
So, the problem is that I gave the matrix constructor got a wrong codomain, namely the category Rings()
--- and my generic __call__
method checks whether the output belongs to the intended category. What should be the right choice?
sage: M.categories() [Category of modules over Integer Ring, Category of bimodules over Integer Ring on the left and Integer Ring on the right, Category of left modules over Integer Ring, Category of right modules over Integer Ring, Category of commutative additive groups, Category of commutative additive monoids, Category of commutative additive semigroups, Category of additive magmas, Category of sets, Category of sets with partial maps, Category of objects]
Since the construction functor can not know about the base ring, I guess CommutativeAdditiveGroups()
would be the way to go.
comment:6 Changed 12 years ago by
I went through the file and found that indeed in some cases wrong categories were chosen. I count this as an argument pro my approach to have a generic __call__
method, because this checks whether the result is in the expected category.
After doing the appropriate changes, I am running ptestlong as well.
comment:7 follow-up: 8 Changed 12 years ago by
Milestone: | → sage-4.5.2 |
---|---|
Status: | needs_work → needs_review |
I produced a new patch (I hope I got the hg -qfold
command right).
The problem was:
- Some construction functors used to be defined on the wrong categories. E.g., the
MatrixFunctor
was defined as a functor from Rings() to Rings(), which is of course wrong if the number of rows is different from the number of columns. - In the good old times, every functor had a custom
__call__
method. Therefore, it was not noticed that sometimes the return value did not belong to the expected category. - My default
__call__
method does check the output - and raises an error if it is wrong. - For some reason I forgot to run
sage -testall
Solution:
- Be more careful with defining domain and codomain of the construction functors.
- Run
make ptestlong
. Result:All tests passed! Total time for all tests: 4078.1 seconds
One remark concerning doctests. The genuinely new code (induced morphisms) is doctested. In my patch, I however did not add tests for sage.categories.pushout. This is done in #8800. I hope that the ticket from #8800 still applies with the new patch that I posted here.
comment:8 Changed 12 years ago by
Replying to SimonKing:
One remark concerning doctests. The genuinely new code (induced morphisms) is doctested. In my patch, I however did not add tests for sage.categories.pushout. This is done in #8800. I hope that the ticket from #8800 still applies with the new patch that I posted here.
Unfortunately, #8800 does not apply with the new patch from here.
Suggestion: I'll rebase #8800 relative to the new patch here. So, #8807 would be reviewed first, and the next to review would be #8800, which contains many doctests. I hope this is acceptable.
comment:9 follow-ups: 10 11 Changed 12 years ago by
Status: | needs_review → needs_work |
---|
Review:
Just a few trivial comments, after which I could give this a positive review. The patch applies fine to 4.6.rc0 (though the related one at #8800 does not then apply cleanly) and all tests pass. There is no time regression (long tests took 667s before and 642s after, using -tp 20).
Here are the minor issues in docstrings:
line 44: "one should implement two methods" -- do you mean three?
_apply_functor_to_morphism: first line of docstring is a copy from the previous function but should presumably be "Apply the functor to a morphism between ... something"
In the new __call__
function, I would like to see a test of the branch which raises a TypeError
""%s is ill-defined, ..."
Is the spelling of "CompositConstructionFunctor
" intentional? Should it not be "CompositeConstructionFunctor
"?
comment:10 Changed 12 years ago by
Hi John!
Replying to cremona:
Review:
Just a few trivial comments, after which I could give this a positive review. The patch applies fine to 4.6.rc0 (though the related one at #8800 does not then apply cleanly) and all tests pass. There is no time regression (long tests took 667s before and 642s after, using -tp 20).
That's good news! As my patch only adds functionality, without changing the method resolution order of existing classes and without replacing existing algorithms, it is no surprise that the speed remains fine.
Here are the minor issues in docstrings:
line 44: "one should implement two methods" -- do you mean three?
You know, there are three types of mathematicians: Some can count, and others can't.
But isn't it pythonesque? Recall the Holy Hand Grenade of Antioch from the movie "Monty Python and the Holy Grail"... :)
_apply_functor_to_morphism: first line of docstring is a copy from the previous function but should presumably be "Apply the functor to a morphism between ... something"
Right.
In the new
__call__
function, I would like to see a test of the branch which raises aTypeError
""%s is ill-defined, ..."
OK, but I hope such example needs to be constructed on purpose. It used to happen with the matrix constructor, for example: The functor was supposed to take a ring R into the ring(!!) of m by n matrices over R. But if the matrix constructor does not produce square matrices, the result is of course not a ring. This bug existed before and is fixed in my patch (now, the functor's codomain is only expected to be the category of rings if m equals n). However, this is exactly the situation that is covered by the TypeError
.
Is the spelling of "
CompositConstructionFunctor
" intentional? Should it not be "CompositeConstructionFunctor
"?
This wasn't my idea. CompositConstructionFunctor
existed earlier (see pushout.py).
As I mentioned on the other ticket, I will be unable to do any programming work at least until next week. But it should be one of the first things I'll do once I'm settled in Jena.
Best regards,
Simon
comment:11 Changed 12 years ago by
Replying to cremona:
... Here are the minor issues in docstrings:
line 44: "one should implement two methods" -- do you mean three?
Corrected.
_apply_functor_to_morphism: first line of docstring is a copy from the previous function but should presumably be "Apply the functor to a morphism between ... something"
Corrected.
In the new
__call__
function, I would like to see a test of the branch which raises aTypeError
""%s is ill-defined, ..."
Done. I define a class that behaves like the matrix constructor used to.
Is the spelling of "
CompositConstructionFunctor
" intentional? Should it not be "CompositeConstructionFunctor
"?
That spelling is old, so, I won't touch it.
I am running sage -tp 3 sage
right now, but I am replacing the old patch in a minute.
Cheers, Simon
comment:12 Changed 12 years ago by
Reviewers: | → John Cremona |
---|---|
Status: | needs_work → needs_review |
OK, patch is updated.
Please only apply trac-8807_induced_morphisms.patch
.
Changed 12 years ago by
Attachment: | trac-8807_induced_morphisms.patch added |
---|
This patch applies to sage-4.6; it is the only patch to be applied
comment:15 follow-up: 16 Changed 12 years ago by
Status: | needs_review → positive_review |
---|
...all long tests pass!
comment:16 Changed 12 years ago by
Status: | positive_review → needs_work |
---|
Replying to cremona:
...all long tests pass!
Sorry, I am a complete idiot. I imported the patch and did sage -b but never qpushed it. Back to square one.
comment:17 Changed 12 years ago by
Status: | needs_work → needs_review |
---|
comment:18 Changed 12 years ago by
Status: | needs_review → positive_review |
---|
Third time lucky: I did apply the patch, and rebuild, and test the entire library with -long, and all tests pass. (4.6.1.alpha2, 64-bit),
comment:19 Changed 12 years ago by
Release manager: after merging this patch, please also do the one at #10318 which has a positive review and just does a lot of spelling corrections, mostly on the file which this one affects most.
comment:20 Changed 12 years ago by
Milestone: | sage-4.6.1 → sage-4.6.2 |
---|
comment:21 Changed 12 years ago by
To the buildbot and the release manager:
Apply trac-8807_induced_morphisms.patch
comment:22 Changed 12 years ago by
Merged in: | → sage-4.6.2.alpha0 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
Implementing induced homomorphisms; Functors on morphisms; some doc tests