Opened 8 years ago
Closed 8 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, GitHub, GitLab) | 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 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Branch set to u/ncohen/16269
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
- Commit set to 370abb8bfc058cb4a3017aa31b880bcdbefc762f
comment:4 follow-up: ↓ 6 Changed 8 years ago by
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:
3702315 | trac #16269: _element_constructor_ in CartesianProduct
|
220ce27 | trac #16269: Finish the previous commits
|
370abb8 | trac #16269: Fixing doctests and implementing additional functions
|
comment:5 follow-up: ↓ 9 Changed 8 years ago by
- 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: ↓ 13 Changed 8 years ago by
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 8 years ago by
Funny, there is no rings.<tab>
thing...
Nathann
comment:8 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:9 in reply to: ↑ 5 ; follow-up: ↓ 11 Changed 8 years ago by
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/discussionIn the meantime, as it seems you cannot call
FiniteEnumeratedSet(a_list)(something)
then it is unavoidableNathann
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 8 years ago by
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 8 years ago by
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 8 years ago by
- Commit changed from 370abb8bfc058cb4a3017aa31b880bcdbefc762f to aa07ba19487569ef26772c51092c4d5342faff7c
Branch pushed to git repo; I updated commit sha1. New commits:
aa07ba1 | trac #16269: Working around "officially not a bug"
|
comment:13 in reply to: ↑ 6 ; follow-ups: ↓ 14 ↓ 15 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
comment:16 Changed 8 years ago by
- Commit changed from aa07ba19487569ef26772c51092c4d5342faff7c to d22e245049e26dd10522d3514603868701a286fb
Branch pushed to git repo; I updated commit sha1. New commits:
d22e245 | trac #16269: missing __iter__
|
comment:17 follow-up: ↓ 18 Changed 8 years ago by
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: ↓ 19 Changed 8 years ago by
Yo !
- CartesianProduct?.iter should be in EnumeratedSets?.CartesianProducts?.ParentMethods?
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: ↓ 20 Changed 8 years ago by
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 inFiniteEnumeratedSet
, 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: ↓ 21 Changed 8 years ago by
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: ↓ 22 Changed 8 years ago by
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: ↓ 25 Changed 8 years ago by
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 8 years ago by
- Commit changed from d22e245049e26dd10522d3514603868701a286fb to 338cc5b99fe50f435d2f6600eea46cffa372305a
comment:24 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
- Commit changed from 338cc5b99fe50f435d2f6600eea46cffa372305a to f67d82e378c4337dcf8cde49d2ca7d6e5b774086
comment:27 Changed 8 years ago by
Here it is ! ;-)
Nathann
comment:28 Changed 8 years ago by
Okay, the problem being solved can I set this to positive_review
? It is the last unreviewed dependency of #16277.
Nathann
comment:29 Changed 8 years ago by
- Branch changed from u/ncohen/16269 to u/nthiery/16269
comment:30 Changed 8 years ago by
- Commit changed from f67d82e378c4337dcf8cde49d2ca7d6e5b774086 to 0a54b68c242cc6541108b709170c35b3a79515b8
Branch pushed to git repo; I updated commit sha1. New commits:
0a54b68 | Trac 16269: little improvements + line folding in the doctest output
|
comment:31 Changed 8 years ago by
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:
0a54b68 | Trac 16269: little improvements + line folding in the doctest output
|
comment:32 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
All long tests pass btw
comment:35 Changed 8 years ago by
- Reviewers set to Nathann Cohen, Nicolas M. Thiéry
- Status changed from needs_review to positive_review
Okayokayokay, thennnnnnnnn ... :-)
Nathann
comment:36 Changed 8 years ago by
- Branch changed from u/nthiery/16269 to u/nthiery/16269-optimized
comment:37 Changed 8 years ago by
- Commit changed from 0a54b68c242cc6541108b709170c35b3a79515b8 to b5ad803eeb1e72e8f276416e7267a351ac314ed2
New commits:
b5ad803 | Trac 16269 (or follow up): optimize CartesianProduct._cartesian_product_of_elements
|
comment:38 Changed 8 years ago by
- Branch changed from u/nthiery/16269-optimized to u/nthiery/16269
- Commit changed from b5ad803eeb1e72e8f276416e7267a351ac314ed2 to 0a54b68c242cc6541108b709170c35b3a79515b8
comment:39 Changed 8 years ago by
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 8 years ago by
The optimization is now #16288, as this was more practical for Nathann. Hence this ticket is ready to be merged as is.
comment:41 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:42 Changed 8 years ago by
- Branch changed from u/nthiery/16269 to 0a54b68c242cc6541108b709170c35b3a79515b8
- Resolution set to fixed
- Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #16269: _element_constructor_ in CartesianProduct
trac #16269: Finish the previous commits
trac #16269: Fixing doctests and implementing additional functions