Use the cythonized versions of has_descent, first_descent, descents for reflection groups

[stumpc5]

These methods are already included in #20445 and should be factored out. That will in particular speed subword complexes a lot, see #20402.

CC: @tscrim @fchapoton @nthiery @sagetrac-vripoll

Component: combinatorics

Reviewer: Christian Stump

Issue created by migration from https://trac.sagemath.org/ticket/20484

[stumpc5]

comment:1

For the record: subword complexes would appreciate fast apply_simple_reflection_left and has_left_descent, see

sage:W = ReflectionGroup(['A',8])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %prun SC = SubwordComplex(Q,W.w0)

4679142 function calls (4679130 primitive calls) in 8.222 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   772419    2.634    0.000    3.119    0.000 complex_reflection_or_generalized_coxeter_groups.py:831(apply_simple_reflection_left)
  1163569    2.464    0.000    2.648    0.000 reflection_group_real.py:771(has_left_descent)
        1    2.229    2.229    7.997    7.997 {sage.combinat.subword_complex_c._construct_facets_c}

[stumpc5]

comment:2

And also:

sage:W = ReflectionGroup(['A',7])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %prun SC = SubwordComplex(Q,W.w0,algorithm="greedy")

         4605779 function calls (4605355 primitive calls) in 8.236 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   560742    1.870    0.000    4.946    0.000 reflection_group_real.py:790(has_descent)
   560742    1.363    0.000    2.774    0.000 coxeter_groups.py:717(has_right_descent)
   560770    1.321    0.000    1.412    0.000 reflection_group_real.py:771(has_left_descent)
   178698    0.744    0.000    5.690    0.000 coxeter_groups.py:763(first_descent)

[fchapoton]

comment:3

I just made a branch. Not having chevie, I have no way to tell if this is faster than before.

---

New commits:

c9bdf03

trac 20484 first try

[fchapoton]

Branch: public/20484

[fchapoton]

Commit: c9bdf03

[tscrim]

comment:4

This was (mostly) taken care of indirectly on #22600.

[tscrim]

Reviewer: Christian Stump

[tscrim]

comment:6

Christian over my laptop concurs.

[fchapoton]

comment:7

Sind Sie in Berlin ?

Would you guys have a little time to look at the failures in the python3-docbuild that are related to crystals ? See there for the log (search for Error: and AttributeError: 'RootSystem' object has no attribute 'dual')

https://patchbot.sagemath.org/log/0/Ubuntu/18.04/x86_64/4.15.0-20-generic/petitbonum/2018-05-27%2021:55:21?plugin=docbuild

[fchapoton]

comment:8

the branch is red..

[tscrim]

Changed commit from c9bdf03 to none

[tscrim]

comment:9

See comment:4

[tscrim]

Changed branch from public/20484 to none

[embray]

comment:10

Presuming these are all correctly reviewed as either duplicate, invalid, or wontfix.