Opened 7 years ago

Last modified 7 years ago

#15305 closed enhancement

Allow natural morphism between tensor products — at Version 14

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:
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

Change History (16)

comment:1 Changed 7 years ago by tscrim

  • Status changed from new to needs_review

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

comment:11 Changed 7 years ago by nborie

For patchbot :

apply trac_15305-coercion_tensor_products-ts.patch

comment:12 Changed 7 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 7 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 7 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 7 years ago by tscrim (previous) (diff)
Note: See TracTickets for help on using tickets.