Sage: Ticket #15305: Allow natural morphism between tensor products
https://trac.sagemath.org/ticket/15305
<p>
Given modules <code>A1, A2, B1, B2</code> with coercions <code>A1 -> B1</code> and <code>A2 -> B2</code>, there is the natural coercion <code>A1 # A2 -> B1 # B2</code> as the tensor of the factor coercions. This ticket implements the above coercion as a natural coercion for <code>CombinatorialFreeModule_Tensor</code>.
</p>
<p>
Apply: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/15305/trac_15305-coercion_tensor_products-ts.patch" title="Attachment 'trac_15305-coercion_tensor_products-ts.patch' in Ticket #15305">trac_15305-coercion_tensor_products-ts.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/15305/trac_15305-coercion_tensor_products-ts.patch" title="Download"></a>
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15305
Trac 1.1.6tscrimFri, 18 Oct 2013 22:46:43 GMTstatus changed
https://trac.sagemath.org/ticket/15305#comment:1
https://trac.sagemath.org/ticket/15305#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketnthierySat, 19 Oct 2013 09:41:16 GMTcc changed
https://trac.sagemath.org/ticket/15305#comment:2
https://trac.sagemath.org/ticket/15305#comment:2
<ul>
<li><strong>cc</strong>
<em>nborie</em> added
</li>
</ul>
<p>
Thanks Travis, that was a long awaited feature.
</p>
<p>
For the test, rather than isinstance(x, CombinatorialFreeModules_Tensor), it would be prefera ble to use x in <a class="missing wiki">ModulesWithBasis?</a>(...).<a class="missing wiki">TensorProducts?</a>().
</p>
<p>
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?
</p>
<p>
Thanks!
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TickettscrimFri, 25 Oct 2013 14:48:35 GMTdependencies set
https://trac.sagemath.org/ticket/15305#comment:3
https://trac.sagemath.org/ticket/15305#comment:3
<ul>
<li><strong>dependencies</strong>
set to <em>#15309</em>
</li>
</ul>
<p>
I've commuted this patch past <a class="closed ticket" href="https://trac.sagemath.org/ticket/15309" title="defect: Symmetric group algebra creating algebra generators using ... (closed: fixed)">#15309</a> and made the change Nicolas T. suggested.
</p>
TickettscrimSat, 02 Nov 2013 05:34:49 GMT
https://trac.sagemath.org/ticket/15305#comment:4
https://trac.sagemath.org/ticket/15305#comment:4
<p>
Didn't factor out everything into <a class="closed ticket" href="https://trac.sagemath.org/ticket/15289" title="enhancement: Implement indexed monoids (closed: fixed)">#15289</a>. Nicolas B. do you have your code on the combinat queue?
</p>
<p>
Best,<br />
Travis
</p>
TicketnborieSat, 02 Nov 2013 10:47:57 GMT
https://trac.sagemath.org/ticket/15305#comment:5
https://trac.sagemath.org/ticket/15305#comment:5
<p>
Hi,
</p>
<p>
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.
</p>
<p>
I am also compiling the last version of Sage... I will have a look on that shortly.
</p>
<p>
Cheers,
Nicolas B.
</p>
TicketnborieSat, 02 Nov 2013 11:50:41 GMT
https://trac.sagemath.org/ticket/15305#comment:6
https://trac.sagemath.org/ticket/15305#comment:6
<p>
Ok, I have read your patch and it look close to I did times ago...
</p>
<p>
In fact, the good way to do this is :
</p>
<ul><li>Make tensor constructor accept a tuple of module morphisms such that if foo and bar are two morphisms between parents inheriting from combinatorialFreeModule :
</li></ul><p>
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)
</p>
<ul><li>Use this improved constructor to return the tensor of coercions
</li></ul><p>
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...
</p>
<p>
I'll try to test your patch on my stack of combinatorial Hopf algebras this week end...
</p>
<p>
Cheers, Nicolas B.
</p>
TickettscrimSat, 02 Nov 2013 21:19:25 GMT
https://trac.sagemath.org/ticket/15305#comment:7
https://trac.sagemath.org/ticket/15305#comment:7
<p>
I accidentally uploaded an old version of the patch. Here's the correct one.
</p>
<p>
I'll wait until Tuesday before looking into defining tensor morphisms.
</p>
TicketnborieTue, 05 Nov 2013 21:01:54 GMT
https://trac.sagemath.org/ticket/15305#comment:8
https://trac.sagemath.org/ticket/15305#comment:8
<p>
After a second look,
</p>
<p>
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 <a class="missing wiki">CartesianProduct?</a> and just iterate on <code></code>im<code></code> instead of CP for the return of the morphism subfunction.
</p>
<p>
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:
</p>
<pre class="wiki">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
</pre><p>
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.
</p>
<p>
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
</p>
<pre class="wiki">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]
</pre><p>
are very nice.
</p>
<p>
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.
</p>
<p>
So, even I really love semantic, I would prefer a speedup version of your patch without the <a class="missing wiki">CartesianProduct?</a> constructor.
</p>
<p>
Do you agree with that ?
Sorry for my English, I hope I am not too much confusing...
</p>
<p>
Cheers and thanks for your work.
</p>
<p>
Nicolas B.
</p>
TickettscrimTue, 05 Nov 2013 21:51:31 GMT
https://trac.sagemath.org/ticket/15305#comment:9
https://trac.sagemath.org/ticket/15305#comment:9
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15305#comment:8" title="Comment 8">nborie</a>:
</p>
<blockquote class="citation">
<p>
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 <a class="missing wiki">CartesianProduct?</a> and just iterate on <code></code>im<code></code> instead of CP for the return of the morphism subfunction.
</p>
</blockquote>
<p>
Could you post the code snippet? I'm using the <code>CartesianProduct</code> to iterate over all of the terms to do the expansion, and I'd like to see how you worked around this.
</p>
<blockquote class="citation">
<p>
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...
</p>
<p>
...
</p>
<p>
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.
</p>
<p>
...
</p>
<p>
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.
</p>
</blockquote>
<p>
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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/15311" title="enhancement: Implement the classical Hall algebra and polynomials (closed: fixed)">#15311</a>).
</p>
<p>
Thanks,<br />
Travis
</p>
TicketnborieTue, 05 Nov 2013 22:01:59 GMT
https://trac.sagemath.org/ticket/15305#comment:10
https://trac.sagemath.org/ticket/15305#comment:10
<p>
I try to just remove <a class="missing wiki">CartesianProduct?</a> replacing
</p>
<pre class="wiki">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])
</pre><p>
by
</p>
<pre class="wiki">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])
</pre><p>
I hope this does not change the result..
</p>
<p>
For curiosity, I attach also the old patch I've made a year ago for Rémi Maurice...
</p>
<p>
Cheers,
</p>
<p>
Nicolas B.
</p>
TicketnborieTue, 05 Nov 2013 22:02:20 GMTattachment set
https://trac.sagemath.org/ticket/15305
https://trac.sagemath.org/ticket/15305
<ul>
<li><strong>attachment</strong>
set to <em>coercion_for_tensor_product-nb.patch</em>
</li>
</ul>
TicketnborieTue, 05 Nov 2013 22:03:49 GMT
https://trac.sagemath.org/ticket/15305#comment:11
https://trac.sagemath.org/ticket/15305#comment:11
<p>
For patchbot :
</p>
<p>
apply trac_15305-coercion_tensor_products-ts.patch
</p>
TickettscrimTue, 05 Nov 2013 22:36:38 GMT
https://trac.sagemath.org/ticket/15305#comment:12
https://trac.sagemath.org/ticket/15305#comment:12
<p>
Here are some timings with my patch (no CP changes):
</p>
<pre class="wiki">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
</pre><p>
With your patch:
</p>
<pre class="wiki">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
</pre><p>
So I'll use your patch with some minor changes.
</p>
TicketnthieryTue, 05 Nov 2013 23:08:04 GMT
https://trac.sagemath.org/ticket/15305#comment:13
https://trac.sagemath.org/ticket/15305#comment:13
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15305#comment:10" title="Comment 10">nborie</a>:
</p>
<blockquote class="citation">
<pre class="wiki">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])
</pre></blockquote>
<p>
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.
</p>
<p>
Btw: doing this might be easier if one extracts a "tensor_product_of_morphisms" function.
</p>
TickettscrimTue, 05 Nov 2013 23:13:10 GMTattachment set
https://trac.sagemath.org/ticket/15305
https://trac.sagemath.org/ticket/15305
<ul>
<li><strong>attachment</strong>
set to <em>trac_15305-coercion_tensor_products-ts.patch</em>
</li>
</ul>
TickettscrimTue, 05 Nov 2013 23:15:34 GMTdescription, author changed; reviewer set
https://trac.sagemath.org/ticket/15305#comment:14
https://trac.sagemath.org/ticket/15305#comment:14
<ul>
<li><strong>reviewer</strong>
set to <em>Nicolas Borie, Travis Scrimshaw</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/15305?action=diff&version=14">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>Travis Scrimshaw</em> to <em>Travis Scrimshaw, Nicolas Borie</em>
</li>
</ul>
<p>
New version timings
</p>
<pre class="wiki">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
</pre><p>
Although it returns a <code>NotImplementedError</code> 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.
</p>
<p>
I found this funny:
</p>
<pre class="wiki">sage -t free_module.py
[666 tests, 1.09 s]
</pre><p>
For patchbot:
</p>
<p>
Apply: trac_15305-coercion_tensor_products-ts.patch
</p>
TickettscrimTue, 05 Nov 2013 23:25:24 GMT
https://trac.sagemath.org/ticket/15305#comment:15
https://trac.sagemath.org/ticket/15305#comment:15
<p>
Well, this is a correct error of sorts:
</p>
<pre class="wiki">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'>
</pre><p>
because <code>MapCombinatorialClass</code> doesn't have a <code>__contains__()</code> method and it's trying to do a conversion (via <code>_element_constructor_()</code>) since there is no coercion.
</p>
<p>
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.
</p>
<p>
For patchbot:
</p>
<p>
Apply: trac_15305-coercion_tensor_products-ts.patch
</p>
TicketnborieWed, 06 Nov 2013 10:39:14 GMTstatus changed
https://trac.sagemath.org/ticket/15305#comment:16
https://trac.sagemath.org/ticket/15305#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
I had not test the whole Sage (Patchbot dosen't want to run tests...) but at least the whole Combinat and categories...
</p>
<p>
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.
</p>
<p>
Ok, perfect for me.
</p>
<p>
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...).
</p>
<p>
Cheers,
</p>
<p>
Nicolas B.
</p>
TickettscrimWed, 06 Nov 2013 17:13:16 GMT
https://trac.sagemath.org/ticket/15305#comment:17
https://trac.sagemath.org/ticket/15305#comment:17
<p>
Thanks for getting to me your version of the patch and for doing the review.
</p>
TickettscrimWed, 06 Nov 2013 18:50:28 GMTkeywords changed
https://trac.sagemath.org/ticket/15305#comment:18
https://trac.sagemath.org/ticket/15305#comment:18
<ul>
<li><strong>keywords</strong>
<em>days54</em> added
</li>
</ul>
TicketjdemeyerSat, 09 Nov 2013 15:30:25 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/15305#comment:19
https://trac.sagemath.org/ticket/15305#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.13.beta3</em>
</li>
</ul>
Ticket