#16926: Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra
-------------------------------------+-------------------------------------
Reporter: nthiery | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/fix_sga-16926 | f15f40cd95cd94cd3e4a3b843fd0b257746d43f0
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by {'newvalue': u'Travis Scrimshaw', 'oldvalue': ''}):
* status: new => needs_review
* author: => Travis Scrimshaw
* cc: virmaux (added)
* branch: => public/combinat/fix_sga-16926
* commit: => f15f40cd95cd94cd3e4a3b843fd0b257746d43f0
Old description:
> We have different implementations of the algebra of the symmetric group,
> and more may come in the future:
> - `SymmetricGroupAlgebra(K, n)`
> - `SymmetricGroup(n).algebra(K)`
> - `WeylGroup(['A',3]).algebra(K)`
> - ...
>
> They mostly differ in how the elements of the symmetric group are
> represented, and each representation can have its advantage depending on
> the application in mind. So it's fine to keep them all. On the other
> hand, currently only the first one makes use of the special features of
> the symmetric group. Here is a plan to share those features across all
> implementations:
>
> Create a category `SymmetricGroups`. Put the relevant groups in this
> category.
>
> Generalize the features (Yucis-Murphy elements, ...) from
> `SymmetricGroupAlgebra` to the category `SymmetricGroups.Algebras`.
>
> Put `SymmetricGroupAlgebra` in this category, and strip away all the code
> that is not needed anymore.
>
> Cross ref the different implementations in the documentation.
>
> Volunteers?
New description:
We have different implementations of the algebra of the symmetric group,
and more may come in the future:
- `SymmetricGroupAlgebra(K, n)`
- `SymmetricGroup(n).algebra(K)`
- `WeylGroup(['A',3]).algebra(K)`
- ...
They mostly differ in how the elements of the symmetric group are
represented, and each representation can have its advantage depending on
the application in mind. So it's fine to keep them all. On the other hand,
currently only the first one makes use of the special features of the
symmetric group. After a discussion, we came up with a plan to share those
features across all implementations:
- Make the categories and functionality as coherent as possible.
- Have `SymmetricGroupAlgebra` take an optional input for the index set.
--
Comment:
Okay, done. So some notes for the reviewer:
- Currently `descents` behavior differs from that given by the category,
so as to avoid backwards incompatible change, we leave warning messages
and leave the behavior alone.
- `reduced_word()` does not respect the order of multiplication and needs
to be fixed so that `TestSuite` passes.
- I've added as much common functionality between `SymmetricGroup` and
`Permutations` since the former is a gap version of the latter. I'm
leaving `WeylGroup` alone because it is a matrix group, but if someone
wants to add better support for conjugacy classes, then go ahead.
- I made a bunch of other optimizations for iterating over elements and
micro-optimizations.
- I abstracted `StandardPermutations_n` to better reflect the mathematics.
- Better and more careful handling of parents during multiplication.
- The `from_*` now can take a parent as input to better control their
output (this was needed).
Some todo's for later:
1. Improve the speed of multiplying Sage permutations:
{{{
sage: S = SymmetricGroup(5)
sage: R = S.simple_reflections()
sage: %timeit prod(R)
10000 loops, best of 3: 36.6 µs per loop
sage: P = Permutations(5)
sage: R = P.simple_reflections()
sage: %timeit prod(R)
1000 loops, best of 3: 413 µs per loop
}}}
2. Refactor the `Permutation` class to better be an element class,
especially parsing of input (hard and tedious).
3. Fix the issues noted above (also hard).
However, IMO the current version should be reviewed and included into Sage
(as it is needed for #11111).
This is the other option, which I am keeping here for the official record:
* Create a category `SymmetricGroups`. Put the relevant groups in this
category.
* Generalize the features (Yucis-Murphy elements, ...) from
`SymmetricGroupAlgebra` to the category `SymmetricGroups.Algebras`.
* Put `SymmetricGroupAlgebra` in this category, and strip away all the
code that is not needed anymore.
* Cross ref the different implementations in the documentation.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=8144d477a29de3bfd56e2f12041066de09772973
8144d47]||{{{Added optional argument for indexing set of SGA.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=a2d9dcd50fb3cc1aac6a1d8ffc2538c61bfecaf6
a2d9dcd]||{{{Initial setting of StandardPermutations_n to be in
FiniteWeylGroups.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=765cbdb27ce49c48c0fb8ed6402345b0de3d4136
765cbdb]||{{{Fixes and tweaks and speedups.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=a63dfd39c3e0ab47239102d10ce55a1e8b711962
a63dfd3]||{{{Added support for conjugacy classes for permutation
groups.}}}||
||[http://git.sagemath.org/sage.git/commit/?id=f15f40cd95cd94cd3e4a3b843fd0b257746d43f0
f15f40c]||{{{Some additional fixes and cleanup.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/16926#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
