Opened 5 years ago

Closed 5 years ago

#16269 closed enhancement (fixed)

Cartesian Products of additive groups

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: categories Keywords:
Cc: nthiery, dimpase, vdelecroix Merged in:
Authors: Nathann Cohen, Nicolas M. Thiéry Reviewers: Nathann Cohen, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: 0a54b68 (Commits) Commit: 0a54b68c242cc6541108b709170c35b3a79515b8
Dependencies: #16280 Stopgaps:

Description

With this branch, one can see the product of two fields (or the product of one field and an additive group) as an additive group.

sage: F8=GF(8,'x') 
sage: x = F8.primitive_element()
sage: F5=GF(5)
sage: F8xF5 = F8.cartesian_product(F5)
sage: F8xF5.an_element()
(0, 0)
sage: e=F8xF5((x,4))    
sage: e
(x, 4)
sage: e+e
(0, 3)
sage: 3*e
(x, 2)
sage: -e
(x, 1)

Change History (42)

comment:1 Changed 5 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by ncohen

  • Branch set to u/ncohen/16269
  • Status changed from needs_review to needs_work

comment:3 Changed 5 years ago by git

  • Commit set to 370abb8bfc058cb4a3017aa31b880bcdbefc762f

Branch pushed to git repo; I updated commit sha1. New commits:

3702315trac #16269: _element_constructor_ in CartesianProduct
220ce27trac #16269: Finish the previous commits
370abb8trac #16269: Fixing doctests and implementing additional functions

comment:4 follow-up: Changed 5 years ago by dimpase

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...


New commits:

3702315trac #16269: _element_constructor_ in CartesianProduct
220ce27trac #16269: Finish the previous commits
370abb8trac #16269: Fixing doctests and implementing additional functions

comment:5 follow-up: Changed 5 years ago by ncohen

  • Cc vdelecroix added

Passes all tests ! The try/except in _element_constructor_ is because of this discussion https://groups.google.com/d/topic/sage-devel/tHallML3OYI/discussion

In the meantime, as it seems you cannot call FiniteEnumeratedSet(a_list)(something) then it is unavoidable

Nathann

comment:6 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by ncohen

Yo !

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...

Hmmmm.. Well, I guess it may not be very hard to do.

1) A ring is a additive group (so the + is already implemented) for the product of rings

2) It has a multiplicative operation, but perhaps the product of multiplicative associative magma is not detected as such. If you can just give Sage the right inheritances, perhaps you have no real code to implement.

Good luck,

Nathann

comment:7 Changed 5 years ago by ncohen

Funny, there is no rings.<tab> thing...

Nathann

comment:8 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:9 in reply to: ↑ 5 ; follow-up: Changed 5 years ago by vdelecroix

Replying to ncohen:

Passes all tests ! The try/except in _element_constructor_ is because of this discussion https://groups.google.com/d/topic/sage-devel/tHallML3OYI/discussion

In the meantime, as it seems you cannot call FiniteEnumeratedSet(a_list)(something) then it is unavoidable

Nathann

Your _element_constructor_ is buggy

sage: S1 = FiniteEnumeratedSet(['a','b','c'])
sage: S2 = GF(5)
sage: C=cartesian_product([S1,S2])
sage: C(('a',1))
('a', 1)
sage: c = C(('a',1))
sage: c[1].parent()
Integer Ring

It would be better to clean the input of the cartesian product set by set.

comment:10 Changed 5 years ago by nthiery

I'd say: don't worry about the Rings thing for now unless you critically need it. It will be a one line to add once #10963 is in. Just handle the additive and multiplicative side separately.

I'll have a look at this later today.

comment:11 in reply to: ↑ 9 Changed 5 years ago by ncohen

Your _element_constructor_ is buggy

Hey man, if it comes to that I think that the design in which the elements of a Parent are not Element is the buggy thing.

Nathann

comment:12 Changed 5 years ago by git

  • Commit changed from 370abb8bfc058cb4a3017aa31b880bcdbefc762f to aa07ba19487569ef26772c51092c4d5342faff7c

Branch pushed to git repo; I updated commit sha1. New commits:

aa07ba1trac #16269: Working around "officially not a bug"

comment:13 in reply to: ↑ 6 ; follow-ups: Changed 5 years ago by dimpase

Replying to ncohen:

Yo !

Hmm, do you mean to construct the Cartesian product of fields? Then it will be a ring, with two operations, addition and multiplication...

Hmmmm.. Well, I guess it may not be very hard to do.

1) A ring is a additive group (so the + is already implemented) for the product of rings

You can make any abelian group into a ring by defining multiplication by a non-zero element a to be identity operation, i.e. ax=x for all x in the group, and by 0 to be zero, i.e. 0x=0 for all x in the group. This should be easy to implement - no real code, just some abstract nonsense :-)

That is, as soon as you have cartesian product of rings, you have what you need in general...

2) It has a multiplicative operation, but perhaps the product of multiplicative associative magma is not detected as such.

but why? Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

If you can just give Sage the right inheritances, perhaps you have no real code to implement.

If I were a category theorist and a (C)Python guru by training, perhaps it will only take me 5 minutes ;-)

comment:14 in reply to: ↑ 13 Changed 5 years ago by ncohen

Yo !

Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

I have no idea what #10963 contains, nor do I care to be honest. And about implementing rings, I would personally chose to behave as if #10963 were to never be merged, because you just can't count on stuff like this to happen :-P

If I were a category theorist and a (C)Python guru by training, perhaps it will only take me 5 minutes ;-)

Which is why I lived very hard the last 2 days, during which I tried to implement a ten-lines patch that would have taken any of the so-called "category theorist and a (C)Python guru by training" those 5 minutes. Besides, I don't consider the product of additive group to be such a weird notion that it could be left unimplemented for years :-P

But well. Now it is done in this patch. Stuff happens.

Nathann

comment:15 in reply to: ↑ 13 Changed 5 years ago by nthiery

Replying to dimpase:

Is it because #10963 will take forever to merge, as it has apparently hit some kind of OSS unsolvability barrier? :)

The review process has restarted :-)

comment:16 Changed 5 years ago by git

  • Commit changed from aa07ba19487569ef26772c51092c4d5342faff7c to d22e245049e26dd10522d3514603868701a286fb

Branch pushed to git repo; I updated commit sha1. New commits:

d22e245trac #16269: missing __iter__

comment:17 follow-up: Changed 5 years ago by nthiery

Hi!

I have just been through the changes. Overall, it looks good, thanks!

Remaining points:

  • CartesianProduct?.iter should be in EnumeratedSets?.CartesianProducts?.ParentMethods?
  • In _add_, self.parent(right) looks suspicious. Does it even work? If the purpose is to convert right into the same parent as self, then no need to worry about this: _add_ may assume that its two arguments belong to the same parent.
  • I am uncomfortable with using iter and getitem for accessing the components of an element. For certain cartesian products (e.g. cartesian products of modules), iter may have a different meaning. Please use summand_split and summand_projection instead.
  • In _element_constructor_: given the catch, if we feed completely unrelated crap to the constructor, is there an exception raised as one could desire?
        sage: GF(3)("a")
        Traceback (most recent call last)
        ...
        TypeError: unable to convert x (=a) to an integer
    
        sage: C = cartesian_product([GF(3), GF(3)])
        sage: C(["a","b"])
        ???
    

Please add this doctest. Btw, one might also want to raise a meaningful error if the length of x is incorrect.

Cheers,

Nicolas

comment:18 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by ncohen

Yo !

Done

  • In _add_, self.parent(right) looks suspicious. Does it even work? If the purpose is to convert right into the same parent as self, then no need to worry about this: _add_ may assume that its two arguments belong to the same parent.

That was the reason. Done.

  • I am uncomfortable with using iter and getitem for accessing the components of an element. For certain cartesian products (e.g. cartesian products of modules), iter may have a different meaning. Please use summand_split and summand_projection instead.

Here I do not agree. This is the most natural definition of an "iter" for a cartesian product. Your application will overrule this anyway, so how can that be a problem ?

  • In _element_constructor_: given the catch, if we feed completely unrelated crap to the constructor, is there an exception raised as one could desire?
        sage: GF(3)("a")
        Traceback (most recent call last)
        ...
        TypeError: unable to convert x (=a) to an integer
    
        sage: C = cartesian_product([GF(3), GF(3)])
        sage: C(["a","b"])
        ???
    

Okay, so here I am stuck and I can't sort this out. Here is the problem :

sage: FiniteEnumeratedSet(["a","b","c"])("a")
TypeError: Cannot convert str to sage.structure.element.Element
sage: FiniteEnumeratedSet(["a","b","c"])("d")
ValueError: d not in {'a', 'b', 'c'}

Because you cannot trust FiniteEnumeratedSet to have a sound __call__ method, I need this try/catch.

On the other hand, if I have this try/catch, then I cannot detect GF(3)("e") anymore. So what do we do ?

I personally see no problem in removing this catch, knowing that cartesian products of FiniteEnumeratedSet will fail. For me it is because of a bug in FiniteEnumeratedSet, not of what I implement.

Nathann

comment:19 in reply to: ↑ 18 ; follow-up: Changed 5 years ago by nthiery

Replying to ncohen:

Here I do not agree. This is the most natural definition of an "iter" for a cartesian product. Your application will overrule this anyway, so how can that be a problem ?

Ah shoot, in the mean time I answered your private e-mail about this :-) Shall I copy paste my answer here?

I personally see no problem in removing this catch, knowing that cartesian products of FiniteEnumeratedSet will fail. For me it is because of a bug in FiniteEnumeratedSet, not of what I implement.

I agree.

If this special situation is not used too much elsewhere (i.e. if all test pass), then I'd say let's go. And if not, I guess we will need to fix/workaround the problem in FiniteEnumeratedSet?.

Cheers,

Nicolas

comment:20 in reply to: ↑ 19 ; follow-up: Changed 5 years ago by ncohen

Yo !

Ah shoot, in the mean time I answered your private e-mail about this :-) Shall I copy paste my answer here?

For others: the answer was that I should just use the .summand_projection commands in the code and not iter on the elements for it could have a different meaning elsewhere.

I asked you how to guess the length of the vector though... Which I will need to call the projection commands.

I agree.

If this special situation is not used too much elsewhere (i.e. if all test pass), then I'd say let's go. And if not, I guess we will need to fix/workaround the problem in FiniteEnumeratedSet?.

Well, not all tests pass actually, I just noticed. The first examples in the doc of categories/cartesian_product use enumerated sets >_<

Nathann

comment:21 in reply to: ↑ 20 ; follow-up: Changed 5 years ago by nthiery

Replying to ncohen:

Well, not all tests pass actually, I just noticed. The first examples in the doc of categories/cartesian_product use enumerated sets >_<

No luck. I can have a shot at fixing/working around the problem in FiniteEnumeratedSets? later tonight if you want.

comment:22 in reply to: ↑ 21 ; follow-up: Changed 5 years ago by ncohen

Yo !

No luck. I can have a shot at fixing/working around the problem in FiniteEnumeratedSets? later tonight if you want.

Wow. Thanks.

Ahem. I don't know what happened to the old Nicolas, but I like this version of yourself :-P

Thanks for your help. I am testing that only the bug produced by the FiniteEnumeratedSet remains in my branch, and all your other remarks should be implemented. I also added an exception (and a test) for the case where the element given to _element_constructor_ has the wrong length.

Nathann

P.S. : Okay, the tests are done. It passes all tests in category/ and sets/ except for the category/cartesian_product.py file. The problem is the .an_element() call at the top of the file.

If it comes to that, we could even overwrite FiniteEnumeratedSet.CartesianProduct.ParentMethod._element_constructor_. Gosh. I almost speak the category slang, now. I am scared.

comment:23 Changed 5 years ago by git

  • Commit changed from d22e245049e26dd10522d3514603868701a286fb to 338cc5b99fe50f435d2f6600eea46cffa372305a

Branch pushed to git repo; I updated commit sha1. New commits:

f262faatrac #16269: Merged with 6.2.rc1
338cc5btrac #16269: Reviewer's remarks

comment:24 Changed 5 years ago by nthiery

  • Dependencies set to #16280

I uploaded a potential fix to the FiniteEnumeratedSet problem on #16280, which I added here as light dependency.

comment:25 in reply to: ↑ 22 Changed 5 years ago by nthiery

Replying to ncohen:

Ahem. I don't know what happened to the old Nicolas, but I like this version of yourself :-P

:-)

Well, currently no teaching, no big ongoing administrative task, and before #10963 is in, I am stuck for long term dev. But don't worry, it's the same me: in the mean time others are cursing me (loud or quietly) for not working on other stuff ... Sight, that's never ending ...

Thanks for your help. I am testing that only the bug produced by the FiniteEnumeratedSet remains in my branch, and all your other remarks should be implemented. I also added an exception (and a test) for the case where the element given to _element_constructor_ has the wrong length.

Sounds good. I'll check that tomorrow.

Gosh. I almost speak the category slang, now. I am scared.

:-)

Good night!

Nicolas

comment:26 Changed 5 years ago by git

  • Commit changed from 338cc5b99fe50f435d2f6600eea46cffa372305a to f67d82e378c4337dcf8cde49d2ca7d6e5b774086

Branch pushed to git repo; I updated commit sha1. New commits:

8ac32c2#16280: Fix call for FiniteEnumeratedSet's of plain Python objects
4e27454#16280: Trivial doctest fixes
f67d82etrac #16269: Merged with #16280

comment:27 Changed 5 years ago by ncohen

Here it is ! ;-)

Nathann

comment:28 Changed 5 years ago by ncohen

Okay, the problem being solved can I set this to positive_review ? It is the last unreviewed dependency of #16277.

Nathann

comment:29 Changed 5 years ago by nthiery

  • Branch changed from u/ncohen/16269 to u/nthiery/16269

comment:30 Changed 5 years ago by git

  • Commit changed from f67d82e378c4337dcf8cde49d2ca7d6e5b774086 to 0a54b68c242cc6541108b709170c35b3a79515b8

Branch pushed to git repo; I updated commit sha1. New commits:

0a54b68Trac 16269: little improvements + line folding in the doctest output

comment:31 Changed 5 years ago by nthiery

If my latest changes are fine with you, this is definitely a positive review on my side.

Running all long doctests now just to make sure.


New commits:

0a54b68Trac 16269: little improvements + line folding in the doctest output

comment:32 Changed 5 years ago by ncohen

Well, the exception is nicer and I think you told me that iter belonged to this class (sorry I moved a lot of stuff around, I probably lost track) but I would like to know why you replaced this self() with _cartesian_product_of_elements.

Nathann

comment:33 Changed 5 years ago by nthiery

This bypasses the constructor checks while being independent of the internal representation.

Oh, no, it does not bypass the constructor in the basic implementation! _cartesian_product_of_element should definitely call element_class directly.

Ok, I can't do it right now. But this can wait for a later ticket too.

comment:34 Changed 5 years ago by nthiery

All long tests pass btw

comment:35 Changed 5 years ago by ncohen

  • Reviewers set to Nathann Cohen, Nicolas M. Thiéry
  • Status changed from needs_review to positive_review

Okayokayokay, thennnnnnnnn ... :-)

Nathann

comment:36 Changed 5 years ago by nthiery

  • Branch changed from u/nthiery/16269 to u/nthiery/16269-optimized

comment:37 Changed 5 years ago by nthiery

  • Commit changed from 0a54b68c242cc6541108b709170c35b3a79515b8 to b5ad803eeb1e72e8f276416e7267a351ac314ed2

New commits:

b5ad803Trac 16269 (or follow up): optimize CartesianProduct._cartesian_product_of_elements

comment:38 Changed 5 years ago by nthiery

  • Branch changed from u/nthiery/16269-optimized to u/nthiery/16269
  • Commit changed from b5ad803eeb1e72e8f276416e7267a351ac314ed2 to 0a54b68c242cc6541108b709170c35b3a79515b8

comment:39 Changed 5 years ago by nthiery

Hi,

I fixed _cartesian_product_of_elements to bypass _element_constructor and other checks, and documented it. Here is the timing difference:

sage: S1 = Sets().example()
sage: S2 = InfiniteEnumeratedSets().example()
sage: C = cartesian_product([S2, S1, S2])
sage: l = tuple([S2.an_element(), S1.an_element(), S2.an_element()])

Without the optimization:

sage: %timeit C._cartesian_product_of_elements(l)
10000 loops, best of 3: 22 µs per loop

With the optimization:

sage: %timeit C._cartesian_product_of_elements(lt)
1000000 loops, best of 3: 922 ns per loop

If you are fine including this in this ticket, please change the branch to u/nthiery/16269-optimized. Otherwise, I'll move this commit to a follow up ticket.

For the record: the tests pass on the cartesian_product.py file. Running all long tests now to be sure.

Cheers,

Nicolas

comment:40 Changed 5 years ago by nthiery

The optimization is now #16288, as this was more practical for Nathann. Hence this ticket is ready to be merged as is.

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

comment:41 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:42 Changed 5 years ago by vbraun

  • Branch changed from u/nthiery/16269 to 0a54b68c242cc6541108b709170c35b3a79515b8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.