#20402: Make subword complexes compatible with real reflection groups
-------------------------------------+-------------------------------------
Reporter: stumpc5 | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-7.2
Component: combinatorics | Resolution:
Keywords: reflection group, | Merged in:
coxeter group, subword complex, | Reviewers:
days80 | Work issues:
Authors: Christian Stump | Commit:
Report Upstream: N/A | 283ccf598079150e16406adc6a5a55b519f8ec26
Branch: u/stumpc5/20402 | Stopgaps:
Dependencies: #11187 |
-------------------------------------+-------------------------------------
Comment (by stumpc5):
Replying to [comment:25 tscrim]:
> For the speed issues, how much of this is making a difference?
{{{
sage: W = ReflectionGroup(['A',5])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %time S = SubwordComplex(Q,W.w0)
CPU times: user 42.7 ms, sys: 612 µs, total: 43.3 ms
Wall time: 39.5 ms
sage: len(S)
132
sage: W = CoxeterGroup(['A',5])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %time S = SubwordComplex(Q,W.w0)
CPU times: user 15.1 s, sys: 84.3 ms, total: 15.1 s
Wall time: 15.1 s
sage: len(S)
132
}}}
The complete implementation depends on {{{has_descents}}} and
multiplication of elements to be fast (and this will get another boost for
{{{ReflectionGroup}}} in #20484), when you {{{%prun}}} the code for
{{{CoxeterGroup}}} you don't see a single bottleneck but that it is too
slow in many parts (I am not complaining about this speed issue in
general, this implementation is uniform for all Coxeter systems, finite or
infinite, so that's great and the speed is what one gets there!)
> If it does, you can separate out the important functionality into a
separate method, and then subclass the general class which special cases
the methods when you use `ReflectionGroup`.
This implementation of subword complexes is **not** a general
implementation that could be moved up the hierarchy, and then a few
methods could be replaced for concrete implementations. All the internal
core methods are written so that internally it only plays with numbers and
permutations of numbers, you only see roots popping out when using the
API.
Is is indeed possible to write a toy (in terms of speed) implementation
for the category of {{{CoxeterGroups}}}, but I am not the one doing that
at the moment -- what I provide is a research level implementation for
{{{ReflectionGroup}}}.
> However, let me be a bit more stern, I will not set this ticket to a
positive review when you essentially remove doctest coverage because
`gap3` is not an optional package yet (although this argument weakens once
it is). Moreover, you can test all of the functionality with standard
Sage, which such tests should be localized to each method, not (only) in a
class-level test which does the "core" functionality.
Hm -- you see my complaints about that above. On the other hand, I also
see your point of getting rotten untested code after a while, and I don't
really care if we pollute the documentation with more tests.
> By renaming `action_on_root_indices`, you need to deprecate it.
It was only there for a few months, see #11010, and this method is almost
surely not used by anyone so far. You still think it should be deprecated
?
> I am okay with you adding an `is_crystallographic` to the group here,
but it might be a little strange if the crystallographic-ness of a Coxeter
group is different than its Coxeter type/matrix.
How could crystallographic-ness being different for the group and for its
Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a
"proof" that the two are the same. Or am I overseeing something?
--
Ticket URL: <http://trac.sagemath.org/ticket/20402#comment:27>
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.
