Opened 7 years ago

Closed 7 years ago

#16925 closed defect (duplicate)

Revert SymmetricGroup.algebra change from #16678

Reported by: nthiery Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords:
Cc: sage-combinat, tscrim, darij, virmaux Merged in:
Authors: Reviewers: Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by nthiery)

#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, Yucis-Murphy elements, ...). However SymmetricGroupAlgebra is not a drop-in 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 7 years ago by nthiery

  • Cc virmaux added
  • Description modified (diff)

comment:2 Changed 7 years ago by nthiery

  • Branch set to u/nthiery/revert_symmetricgroup_algebra_change_from__16678

comment:3 follow-up: Changed 7 years ago by darij

  • Commit set to 479fddb4afe86e8dc5382f50e0d8d0d11913e23a

I have a request. Could you add the fact that SymmetricGroup.algebra() != SymmetricGroupAlgebra to the doc, along with an explanation of how to get the SymmetricGroupAlgebra? Thanks.


New commits:

479fddb16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing

comment:4 in reply to: ↑ 3 Changed 7 years ago by nthiery

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 the SymmetricGroupAlgebra? 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 follow-up: Changed 7 years ago by darij

Oops, I meant adding a mention of this to the class-wide doc. Overshadowing the method solely for this sake is too much of a hassle, sorry.

comment:6 in reply to: ↑ 5 Changed 7 years ago by nthiery

Replying to darij:

Oops, I meant adding a mention of this to the class-wide 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 flip-flop.

comment:7 Changed 7 years ago by git

  • Commit changed from 479fddb4afe86e8dc5382f50e0d8d0d11913e23a to ce71c7444f957da20f6f9bd1cda95fde8feda9b1

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

ce71c7416925: updated a few doctests according to the previous commit

comment:8 Changed 7 years ago by nthiery

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

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

comment:9 Changed 7 years ago by virmaux

Looks good to me...

comment:10 Changed 7 years ago by nthiery

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 Permutations. 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 follow-up: Changed 7 years ago by 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.

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 7 years ago by tscrim

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 ; follow-up: Changed 7 years ago by nthiery

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 K-free 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 the SymmetricGroup 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 7 years ago by tscrim

Replying to nthiery:

    sage: S = DihedralGroup(3)
    sage: S.algebra?
    ... provided by Sets.ParentMethods.algebra ...
    This returns the K-free 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 K-module 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 ms

But 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 Permutations 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 nthiery

  • 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:16 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

reviewer name

comment:17 Changed 7 years ago by darij

  • Branch u/nthiery/revert_symmetricgroup_algebra_change_from__16678 deleted
  • Commit ce71c7444f957da20f6f9bd1cda95fde8feda9b1 deleted

comment:18 Changed 7 years ago by nthiery

  • Authors Nicolas M. Thiéry deleted
  • 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 vbraun

  • Status changed from positive_review to needs_work

there is no branch, did you delete it accidentally?

comment:20 Changed 7 years ago by darij

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 tscrim

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from needs_work to positive_review

The milestone wasn't changed to duplicate.

comment:22 Changed 7 years ago by vbraun

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.