Opened 6 years ago

Closed 3 years ago

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

Reported by: Owned by: stumpc5 major sage-duplicate/invalid/wontfix combinatorics tscrim, chapoton, nthiery, vripoll Christian Stump N/A

### Description

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

### comment:1 Changed 6 years ago by stumpc5

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}
```

### comment:2 Changed 6 years ago by stumpc5

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)
```

### comment:3 Changed 5 years ago by chapoton

• Branch set to public/20484

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`

### comment:4 Changed 4 years ago by tscrim

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

### comment:5 Changed 4 years ago by tscrim

• Milestone changed from sage-7.2 to sage-duplicate/invalid/wontfix
• Status changed from new to needs_review

### comment:6 Changed 4 years ago by tscrim

• Reviewers set to Christian Stump
• Status changed from needs_review to positive_review

Christian over my laptop concurs.

### comment:7 Changed 4 years ago by chapoton

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'`)

### comment:8 Changed 4 years ago by chapoton

the branch is red..

### comment:9 Changed 4 years ago by tscrim

• Branch public/20484 deleted