Opened 5 years ago

Closed 5 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 tscrim)

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.

Apply: trac_15305-coercion_tensor_products-ts.patch

Attachments (2)

coercion_for_tensor_product-nb.patch (2.4 KB) - added by nborie 5 years ago.
trac_15305-coercion_tensor_products-ts.patch (4.5 KB) - added by tscrim 5 years ago.

Download all attachments as: .zip

Change History (21)

comment:1 Changed 5 years ago by tscrim

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by nthiery

  • Cc nborie added

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!

Nicolas

comment:3 Changed 5 years ago by tscrim

  • Dependencies set to #15309

I've commuted this patch past #15309 and made the change Nicolas T. suggested.

comment:4 Changed 5 years ago by tscrim

Didn't factor out everything into #15289. Nicolas B. do you have your code on the combinat queue?

Best,
Travis

comment:5 Changed 5 years ago by nborie

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 5 years ago by nborie

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 5 years ago by tscrim

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: Changed 5 years ago by nborie

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 5 years ago by tscrim

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: Changed 5 years ago by nborie

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 5 years ago by nborie

comment:11 Changed 5 years ago by nborie

For patchbot :

apply trac_15305-coercion_tensor_products-ts.patch

comment:12 Changed 5 years ago by tscrim

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 5 years ago by nthiery

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.

comment:14 Changed 5 years ago by tscrim

  • Authors changed from Travis Scrimshaw to Travis Scrimshaw, Nicolas Borie
  • 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]

For patchbot:

Apply: trac_15305-coercion_tensor_products-ts.patch

Last edited 5 years ago by tscrim (previous) (diff)

comment:15 Changed 5 years ago by tscrim

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 5 years ago by nborie

  • 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 5 years ago by tscrim

Thanks for getting to me your version of the patch and for doing the review.

comment:18 Changed 5 years ago by tscrim

  • Keywords days54 added

comment:19 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.13.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.