Allow natural morphism between tensor products

[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​

[nthiery]

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

[tscrim]

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

[tscrim]

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

Best,
Travis

[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.

[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.

[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.

[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.

[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

[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.

[nborie]

For patchbot :

apply trac_15305-coercion_tensor_products-ts.patch

[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.

[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.

[tscrim]

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