Opened 7 years ago
Closed 7 years ago
#15305 closed enhancement (fixed)
Allow natural morphism between tensor products
Reported by: | tscrim | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | coercion | Keywords: | tensor product coercion, days54 |
Cc: | sage-combinat, nthiery, SimonKing, nborie | Merged in: | sage-5.13.beta3 |
Authors: | Travis Scrimshaw, Nicolas Borie | Reviewers: | Nicolas Borie, Travis Scrimshaw |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #15309 | Stopgaps: |
Description (last modified by )
Given modules A1, A2, B1, B2
with coercions A1 -> B1
and A2 -> B2
, there is the natural coercion A1 # A2 -> B1 # B2
as the tensor of the factor coercions. This ticket implements the above coercion as a natural coercion for CombinatorialFreeModule_Tensor
.
Attachments (2)
Change History (21)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Cc nborie added
comment:3 Changed 7 years ago by
- Dependencies set to #15309
I've commuted this patch past #15309 and made the change Nicolas T. suggested.
comment:4 Changed 7 years ago by
Didn't factor out everything into #15289. Nicolas B. do you have your code on the combinat queue?
Best,
Travis
comment:5 Changed 7 years ago by
Hi,
No, the code that Nicolas was speaking about was a patch on my last (and died) laptop. I do not have it now but I wrote it (8 months ago) and I probably installed a copy on the Remi Maurice desktop at Marne. I will try to check that on this Monday.
I am also compiling the last version of Sage... I will have a look on that shortly.
Cheers, Nicolas B.
comment:6 Changed 7 years ago by
Ok, I have read your patch and it look close to I did times ago...
In fact, the good way to do this is :
- Make tensor constructor accept a tuple of module morphisms such that if foo and bar are two morphisms between parents inheriting from combinatorialFreeModule :
tensor( (foo, bar) ) return the module morphism from tensor( (foo.domain(), bar.domain()) ) to tensor( (foo.codomain(), bar.codomain()) ) (and doing what you think so hard)
- Use this improved constructor to return the tensor of coercions
Even I had this advise from Nicolas T., I did not implemented it this way. I choose an approach like you do. I try to remember why but I completely forget why I did not the nice way. The reason can be laziness from me or a technical issue. I completely forget...
I'll try to test your patch on my stack of combinatorial Hopf algebras this week end...
Cheers, Nicolas B.
comment:7 Changed 7 years ago by
I accidentally uploaded an old version of the patch. Here's the correct one.
I'll wait until Tuesday before looking into defining tensor morphisms.
comment:8 follow-up: ↓ 9 Changed 7 years ago by
After a second look,
My code did things exactly like you do (I mean I have no more interesting proposition). For your current implementation, we win a 20% speedup without using the constructor CartesianProduct? and just iterate on im
instead of CP for the return of the morphism subfunction.
About design, I had a discussion with Rémi Maurice (king of combinatorial Hopf algebras implementation in Marne). Your patch and also the drafty one I did have the same problem : we check the existence of "natural" morphism by looking for coercion on atomic parent composing domain and codomain position-wise. This doesn't catch everything from far... Even we forgive about permutation of atoms in tensor product, this cut in atoms is the best solution we currently have. This make the following problem:
sage: C1 = CombinatorialFreeModule(ZZ, ZZ) sage: S1 = C1.tensor(C1) sage: f = S1.module_morphism(on_basis = lambda x : C1.monomial(x[0])+C1.monomial(x[1]), codomain=C1) sage: f.register_as_coercion() sage: C1(S1.an_element()) 3*B[-1] + 9*B[0] + 2*B[1] sage: S2 = S1.tensor(S1) sage: S2.has_coerce_map_from(S1) False
If A tensor A has coercion to B, we don't cath the "natural" coercion from (A tensor A) tensor (A tensor A) to B tensor B.
That said, this ticket doesn't intend to solve the full research of coercion between any couple of (tensor)combinatorial free module and this could be very fun to have it rapidly in Sage since things like
sage: P = SymmetricFunctions(QQ).p(); P Symmetric Functions over Rational Field in the powersum basis sage: M = SymmetricFunctions(QQ).m(); M Symmetric Functions over Rational Field in the monomial basis sage: E = SymmetricFunctions(QQ).e(); E Symmetric Functions over Rational Field in the elementary basis sage: S = SymmetricFunctions(QQ).s(); S Symmetric Functions over Rational Field in the Schur basis sage: A = tensor((P, S)) sage: B = tensor((E, M)) sage: A(B.an_element()) 2*p[] # s[] + 2*p[] # s[1] - 3*p[] # s[1, 1] + 3*p[] # s[2]
are very nice.
For the test of all permutations on atoms of a tensor product and each parenthesis configuration on atoms and perhaps a coercion..... We think it is not a good thing to check such loud thing every time. For these cases (in which most of the time, the user know very well which is the permutation and the packaging of the atoms for (co)domain), we should have a nice tensor constructor which accept a tuple of morphisms (and after the construction, we forgive the parenthesis cutting into atoms new domain and new codomain). This should leave in a different ticket letting all current tensor product in Sage benefit from this enhancement.
So, even I really love semantic, I would prefer a speedup version of your patch without the CartesianProduct? constructor.
Do you agree with that ? Sorry for my English, I hope I am not too much confusing...
Cheers and thanks for your work.
Nicolas B.
comment:9 in reply to: ↑ 8 Changed 7 years ago by
Replying to nborie:
My code did things exactly like you do (I mean I have no more interesting proposition). For your current implementation, we win a 20% speedup without using the constructor CartesianProduct? and just iterate on
im
instead of CP for the return of the morphism subfunction.
Could you post the code snippet? I'm using the CartesianProduct
to iterate over all of the terms to do the expansion, and I'd like to see how you worked around this.
About design, I had a discussion with Rémi Maurice (king of combinatorial Hopf algebras implementation in Marne). Your patch and also the drafty one I did have the same problem : we check the existence of "natural" morphism by looking for coercion on atomic parent composing domain and codomain position-wise. This doesn't catch everything from far...
...
If A tensor A has coercion to B, we don't cath the "natural" coercion from (A tensor A) tensor (A tensor A) to B tensor B.
...
For these cases (in which most of the time, the user know very well which is the permutation and the packaging of the atoms for (co)domain), we should have a nice tensor constructor which accept a tuple of morphisms (and after the construction, we forgive the parenthesis cutting into atoms new domain and new codomain). This should leave in a different ticket letting all current tensor product in Sage benefit from this enhancement.
I agree that this misses many natural maps and would definitely be a nice feature to have. I also agree that this should wait for a later ticket (since I'm just using this to make thing easier for #15311).
Thanks,
Travis
comment:10 follow-up: ↓ 13 Changed 7 years ago by
I try to just remove CartesianProduct? replacing
def tensor_morphism(t): im = [M(R._sets[i].monomial(t[i])) for i,M in enumerate(self._sets)] C = CartesianProduct(*im) return self.sum_of_terms([(tuple(x[0] for x in cp), B.prod(x[1] for x in cp)) for cp in C])
by
def tensor_morphism(t): im = [M(R._sets[i].monomial(t[i])) for i,M in enumerate(self._sets)] return self.sum_of_terms([(tuple(x[0] for x in cp), B.prod(x[1] for x in cp)) for cp in im])
I hope this does not change the result..
For curiosity, I attach also the old patch I've made a year ago for Rémi Maurice...
Cheers,
Nicolas B.
Changed 7 years ago by
comment:11 Changed 7 years ago by
For patchbot :
apply trac_15305-coercion_tensor_products-ts.patch
comment:12 Changed 7 years ago by
Here are some timings with my patch (no CP changes):
sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 1.01 ms per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 1.01 ms per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 1.04 ms per loop
With your patch:
sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 482 us per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 489 us per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 485 us per loop
So I'll use your patch with some minor changes.
comment:13 in reply to: ↑ 10 Changed 7 years ago by
Replying to nborie:
def tensor_morphism(t): im = [M(R._sets[i].monomial(t[i])) for i,M in enumerate(self._sets)] return self.sum_of_terms([(tuple(x[0] for x in cp), B.prod(x[1] for x in cp)) for cp in im])
In the above, M(...) calls a conversion morphism from R._sets[i] to M. More often than not, that morphism will be a module_morphism, and thus have a "on_basis" method. So if we request once for all the morphism, on could rewrite it as just phi.on_basis(t[i]), avoiding a lot of the overhead.
Btw: doing this might be easier if one extracts a "tensor_product_of_morphisms" function.
Changed 7 years ago by
comment:14 Changed 7 years ago by
- Description modified (diff)
- Reviewers set to Nicolas Borie, Travis Scrimshaw
New version timings
sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 316 us per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 317 us per loop sage: %timeit S2(S.an_element()) 1000 loops, best of 3: 321 us per loop
Although it returns a NotImplementedError
when the coercion is not defined, which is the wrong kind of error, but at least it is an error. I'll see if I can fix this.
I found this funny:
sage -t free_module.py [666 tests, 1.09 s]
comment:15 Changed 7 years ago by
Well, this is a correct error of sorts:
sage: C = CombinatorialFreeModule(ZZ, Set([1,2])) sage: T = tensor((C,C)) sage: T._basis_keys Image of Cartesian product of {1, 2}, {1, 2} by <type 'tuple'> sage: type(_) <class 'sage.combinat.combinat.MapCombinatorialClass'>
because MapCombinatorialClass
doesn't have a __contains__()
method and it's trying to do a conversion (via _element_constructor_()
) since there is no coercion.
I've added you to the authors since the main part of the code is yours and we'll "cross review" this. I'm happy with the current state of the patch.
For patchbot:
Apply: trac_15305-coercion_tensor_products-ts.patch
comment:16 Changed 7 years ago by
- Status changed from needs_review to positive_review
I had not test the whole Sage (Patchbot dosen't want to run tests...) but at least the whole Combinat and categories...
Nevertheless, I hope the green mark will be coming soon and I am pretty sure it is on the way. The current state of the patch seems good and it makes what we want exactly. I did use Sage 5.12 with the dependency to review that. There are also now nice tests on this enhancement.
Ok, perfect for me.
Thanks you very very much for this work. My original fix has been implemented during the Sage days at Providence (9 month ago???) and I lazily never took the time to finalize that (I say that keeping my armor Nicolas T., don't kick me...). In this time of fpsac submission, thanks very much Travis for having finalize it. I am a little ghostly on the Sage trac the last months (position audition and teaching...).
Cheers,
Nicolas B.
comment:17 Changed 7 years ago by
Thanks for getting to me your version of the patch and for doing the review.
comment:18 Changed 7 years ago by
- Keywords days54 added
comment:19 Changed 7 years ago by
- Merged in set to sage-5.13.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
Thanks Travis, that was a long awaited feature.
For the test, rather than isinstance(x, CombinatorialFreeModules_Tensor), it would be prefera ble to use x in ModulesWithBasis?(...).TensorProducts?().
Nicolas B.: you had code to do exactly that, and implementing at that occasion tensor product of morphisms; could you review this patch, and merge with your code?
Thanks!