Opened 8 years ago
Closed 7 years ago
#16925 closed defect (duplicate)
Revert SymmetricGroup.algebra change from #16678
Reported by:  nthiery  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  combinatorics  Keywords:  
Cc:  sagecombinat, tscrim, darij, virmaux  Merged in:  
Authors:  Reviewers:  Nicolas M. Thiéry  
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
#16678 makes SymmetricGroup(n).algebra(K)
return SymmetricGroupAlgebra(K,n)
.
This is nice in principle since SymmetricGroupAlgebra
makes use of the specific properties of the symmetric group to provide more features (better implementation of the center, YucisMurphy elements, ...). However SymmetricGroupAlgebra
is not a dropin replacement for the plain group algebra of the symmetric group. In particular it breaks several assumptions of .algebra
like the fact that the basis of G.algebra(K)
is indexed by elements of G
(here the basis is indexed by plain Permutation
's); it is therefore likely to create bugs and confusion.
This ticket reverts SymmetricGroup.algebra
to the default behavior. See #16926 for a proper plan to endow it with the additional structure of SymmetricGroupAlgebra
.
Change History (22)
comment:1 Changed 8 years ago by
 Cc virmaux added
 Description modified (diff)
comment:2 Changed 8 years ago by
 Branch set to u/nthiery/revert_symmetricgroup_algebra_change_from__16678
comment:3 followup: ↓ 4 Changed 8 years ago by
 Commit set to 479fddb4afe86e8dc5382f50e0d8d0d11913e23a
comment:4 in reply to: ↑ 3 Changed 8 years ago by
Replying to darij:
I have a request. Could you add the fact that
SymmetricGroup.algebra() != SymmetricGroupAlgebra
to the doc, along with an explanation of how to get theSymmetricGroupAlgebra
? Thanks.
I considered this. It means leaving an algebra method in SymmetricGroup? that does nothing but the standard thing, except for having an extra chunk of doc advertising SymmetricGroupAlgebra? and the backward incompatibility issue. I can do that if you think that's helpful for the user.
Right now, I am running all tests after just stripping away the method.
comment:5 followup: ↓ 6 Changed 8 years ago by
Oops, I meant adding a mention of this to the classwide doc. Overshadowing the method solely for this sake is too much of a hassle, sorry.
comment:6 in reply to: ↑ 5 Changed 8 years ago by
Replying to darij:
Oops, I meant adding a mention of this to the classwide doc. Overshadowing the method solely for this sake is too much of a hassle, sorry.
I am still hesitant actually. It's still nice to the user to warn him about the backward incompatibility flipflop.
comment:7 Changed 8 years ago by
 Commit changed from 479fddb4afe86e8dc5382f50e0d8d0d11913e23a to ce71c7444f957da20f6f9bd1cda95fde8feda9b1
Branch pushed to git repo; I updated commit sha1. New commits:
ce71c74  16925: updated a few doctests according to the previous commit

comment:8 Changed 8 years ago by
 Status changed from new to needs_review
With the last commit, all tests passed. Haven't run long tests pass. Let's see what the bot says.
comment:9 Changed 8 years ago by
Looks good to me...
comment:10 Changed 8 years ago by
For the record: it's actually a piece of luck that e.g. hecke_algebra_representations only needed a doctest update. The data structure of the element that was created behind the scene was actually corrupted since a term was internaly indexed by an element of SymmetricGroup
whereas in the SymmetricGroupAlgebra
elements are supposed to be indexed by Permutation
s. Any further operation on it would have lead to an explosion.
Granted: the overall infrastructure should have trapped the creation of such corrupt element; but that's a different discussion ...
comment:11 followup: ↓ 13 Changed 8 years ago by
I'm not quite sure about the (unwritten as far I can tell) assumption that G.algebra
has a basis indexed by the elements of the group.
Here are some timings of the two implementations:
sage: S = SymmetricGroup(3) sage: SGA = SymmetricGroupAlgebra(QQ, 3) sage: GA = GroupAlgebra(S, QQ) sage: %timeit L = list(GA.basis()) 10 loops, best of 3: 23.3 ms per loop sage: %timeit SL = list(SGA.basis()) 1000 loops, best of 3: 775 µs per loop sage: L = list(GA.basis()) sage: SL = list(SGA.basis()) sage: %timeit sum(L) 1000 loops, best of 3: 357 µs per loop sage: %timeit sum(SL) 1000 loops, best of 3: 336 µs per loop sage: %timeit prod(L) 1000 loops, best of 3: 466 µs per loop sage: %timeit prod(SL) 1000 loops, best of 3: 1.28 ms per loop sage: %timeit sum(L)^2 100 loops, best of 3: 2.26 ms per loop sage: %timeit sum(SL)^2 100 loops, best of 3: 7.68 ms per loop
So getting the basis is significantly slower using the generic code, but multiplying elements is faster using the group.
Also going from the permutation group elements to a permutation is fast:
sage: lst = list(S) sage: %timeit Permutation(lst[4]) 10000 loops, best of 3: 69 µs per loop
although there is a slight bug:
sage: P3 = Permutations(3) sage: P3(lst[4]) TypeError: object of type 'sage.groups.perm_gps.permgroup_element.PermutationGroupElement' has no len()
Multiplying permutation group elements is really fast compared to Sage's permutations:
sage: %timeit prod(lst) 100000 loops, best of 3: 2.27 µs per loop sage: P3L = list(Permutations(3)) sage: %timeit prod(P3L) 1000 loops, best of 3: 446 µs per loop
So my proposal would be to change the indexing set of SymmetricGroupAlgebra
to be the SymmetricGroup
and add conversions to Sage's permutations where necessary.
comment:12 Changed 8 years ago by
Minor technical challenge (or perhaps question), we will have to deal with handling backwards compatibility with giving the basis an instance of our Permutation
class.
comment:13 in reply to: ↑ 11 ; followup: ↓ 14 Changed 8 years ago by
Hi Travis,
Thanks for the timings!
Replying to tscrim:
I'm not quite sure about the (unwritten as far I can tell) assumption that
G.algebra
has a basis indexed by the elements of the group.
sage: S = DihedralGroup(3) sage: S.algebra? ... provided by Sets.ParentMethods.algebra ... This returns the Kfree module with basis indexed by S, endowed with whatever structure can be induced from that of S. ...
So any subclass overriding algebra
should satisfy those premises.
Here are some timings of the two implementations: ... So getting the basis is significantly slower using the generic code,
To be precise: in both cases, the implementation of basis
is the
same (provided by ModulesWithBasis?). What we are seeing here is that
iterating through
SymmetricGroup(n)
is slower than iteration through
Permutations(n)
. Actually ridiculously slower:
sage: S = SymmetricGroup(6) sage: %time l = list(S) CPU times: user 1.05 s, sys: 29.2 ms, total: 1.08 s Wall time: 1.19 s sage: S = Permutations(6) sage: %time l = list(S) CPU times: user 27.6 ms, sys: 13.4 ms, total: 41 ms Wall time: 34.2 ms
In principle the complexity should be fairly similar, even for a
generic permutation group implementation; there really must be a
glitch in the GAP/Sage communication given that GAP itself is about as
fast as Permutations
:
sage: S = gap("SymmetricGroup(6)") sage: %time l = S.List() CPU times: user 21.7 ms, sys: 0 ns, total: 21.7 ms Wall time: 33.9 ms
But we are deviating here. That's for a separate ticket.
So my proposal would be to change the indexing set of
SymmetricGroupAlgebra
to be theSymmetricGroup
and add conversions to Sage's permutations where necessary.
This would be even more backward incompatible: people have been using
SymmetricGroupAlgebra
for a long while, and some may have a specific
need for having it indexed by plain permutations. I prefer the
approach outlined here and in #16926.
Cheers,
Nicolas
comment:14 in reply to: ↑ 13 Changed 8 years ago by
Replying to nthiery:
sage: S = DihedralGroup(3) sage: S.algebra? ... provided by Sets.ParentMethods.algebra ... This returns the Kfree module with basis indexed by S, endowed with whatever structure can be induced from that of S. ...So any subclass overriding
algebra
should satisfy those premises.
I didn't interpret that as a contract, but just instead a statement about what the generic method returns. I think some more terse language is needed, such as adding "All classes overriding this method must return a Kmodule with basis indexed by S".
In principle the complexity should be fairly similar, even for a generic permutation group implementation; there really must be a glitch in the GAP/Sage communication given that GAP itself is about as fast as
Permutations
:sage: S = gap("SymmetricGroup(6)") sage: %time l = S.List() CPU times: user 21.7 ms, sys: 0 ns, total: 21.7 ms Wall time: 33.9 msBut we are deviating here. That's for a separate ticket.
It's possible that GAP is also slow, and I get similar behavior when using the Weyl group. However this is definitely something for a separate ticket.
This would be even more backward incompatible: people have been using
SymmetricGroupAlgebra
for a long while, and some may have a specific need for having it indexed by plain permutations. I prefer the approach outlined here and in #16926.
It's (relatively) easy to get Sage's Permutation
s to compare equal to permutation group elements, as perm gp elts have a method called _gap_list
, which returns the oneline notation and compares correctly to a Permutation
. We would also need to change the hash for a (standard) Permutation
to return a hash of the tuple of self (and we could do this generically by doing this first and if we need a fallback, use the hash of the string representation). This should allow the basis to take a Permutation
and return the correct element (plus IMO they really should compare properly anyways).
At the end of the day, the biggest thing I don't like is having a generic implementation when there is a specialized implementation (which we agree on I believe). Reverting the change and having more classes (even with a good ABC) seems like a much harder maintenance task in the long run.
comment:15 Changed 7 years ago by
 Status changed from needs_review to positive_review
This can be set to duplicate of #16926 which is ready to go. We don't need anymore this intermediate step.
comment:17 Changed 7 years ago by
 Branch u/nthiery/revert_symmetricgroup_algebra_change_from__16678 deleted
 Commit ce71c7444f957da20f6f9bd1cda95fde8feda9b1 deleted
comment:18 Changed 7 years ago by
 Reviewers set to Nicolas M. Thiéry
 Status changed from needs_work to positive_review
Thanks Volker for the notice.
comment:19 Changed 7 years ago by
 Status changed from positive_review to needs_work
there is no branch, did you delete it accidentally?
comment:20 Changed 7 years ago by
I deleted it because this branch is obsolete and a dead end. Or was this a wrong assumption?
comment:21 Changed 7 years ago by
 Milestone changed from sage6.4 to sageduplicate/invalid/wontfix
 Status changed from needs_work to positive_review
The milestone wasn't changed to duplicate.
comment:22 Changed 7 years ago by
 Resolution set to duplicate
 Status changed from positive_review to closed
I have a request. Could you add the fact that
SymmetricGroup.algebra() != SymmetricGroupAlgebra
to the doc, along with an explanation of how to get theSymmetricGroupAlgebra
? Thanks.New commits:
16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing