#11187: Implementation of finite reflection groups
-------------------------------------+-------------------------------------
Reporter: stumpc5 | Owner: tbd
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.2
Component: combinatorics | Resolution:
Keywords: reflection group, | Merged in:
days49, days 64.5 | Reviewers:
Authors: Christian Stump | Work issues:
Report Upstream: N/A | Commit:
Branch: | e2f919fa6529b2444dbec4cfffde671b8927d1b7
u/vripoll/11187-new | Stopgaps:
Dependencies: #20107 |
-------------------------------------+-------------------------------------
Changes (by tscrim):
* cc: hivert (added)
* commit: 3da1ebb8a47bdd4ff2c36761b15e663c6d2485fe =>
e2f919fa6529b2444dbec4cfffde671b8927d1b7
* milestone: sage-7.1 => sage-7.2
Comment:
Continuing the discussion from #13580.
Replying to [ticket:13580comment:102 hivert]:
> Replying to [ticket:13580comment:101 tscrim]:
> > Christian, Vivien, and I are working on trying to speed up the
iteration of
> > finite Coxeter groups by using (subgroups of) permutation groups and
the
> > iterator method of generic Coxeter groups, which uses a `SearchForest`
(see
> > #11187 and the `CoxeterGroups` category). Our goal is to try and match
or
> > beat GAP3 iteration time (which we are about ~30x slower).
>
> I'll be both very happy and interested to have usecase for this code.
This will have the more serious use case I know of (the code in the
generic Coxeter groups iterator, e.g., via `CoxeterGroup`, has not had any
serious optimization attempts AFAIK).
> > We are in the process pushing our successor computation code to Cython
and
> > some of our other methods, but we would appreciate any insights you
have.
>
> Do you have a typical example relying on {{{SearchForest}}} of code on
top of
> #11187 that I can profile ? Note that I included in the documentation of
> map_reduce.py a guide on how to profile the parallel code. I'd like to
measure
> the proportion of time that is spend on Coxeter code one one hand and on
the
> parallel infrastructure on the other.
Our current test cases are B,,6,, (~0.5s) and E,,7,, (~1m).
> Now, concerning coxeter group, I'm quite sure that rewriting part of the
code
> in C/C++ and using advanced parallel stuff (AVX instruction set + SIMD)
you
> can get speedup a large as several hundreds and even thousand ! As a
witness
> on https://github.com/hivert/IVMPG I wrote a code whose goal is to
enumerate
> integer vector modulo permutation group. Compared to the code we have in
Sage
> which has been Cythonized and optimized by Simon King I manage to get
speedup
> a large as x2000 ! I need help on the build system to be able to
distribute
> it. I'm pretty sure the code there is very similar to what you need in
Coxeter
> groups.
One of the thoughts I'm bouncing around is doing a full C/C++ version
using arrays, and then using Cython (mainly `PermutationGroupElement`) as
a transfer layer to Sage/GAP. In which case it probably should be split
off as a little specialized spkg.
That is quite an impressive speedup. I know a little bit about build
systems (and its on my todo to learn more for fixing up coxeter3/LiE too),
but, e.g., Jeroen or François are good people to ask. Although if you need
GCC 5.x, then we will need to do some changes to Sage. Yet, I think moving
to GCC 5.x is something that we want and are going to do soon...
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=e2f919fa6529b2444dbec4cfffde671b8927d1b7
e2f919f]||{{{New iterator for real reflection groups.}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/11187#comment:134>
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 https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
