Opened 3 years ago

Closed 8 months ago

#20484 closed enhancement (invalid)

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

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics Keywords:
Cc: tscrim, chapoton, nthiery, vripoll Merged in:
Authors: Reviewers: Christian Stump
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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

Change History (10)

comment:1 Changed 3 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 3 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 3 years ago by chapoton

  • Branch set to public/20484
  • Commit set to c9bdf03eb93aad748849c366229a2d4e610c90ce

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


New commits:

c9bdf03trac 20484 first try

comment:4 Changed 17 months ago by tscrim

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

comment:5 Changed 17 months ago by tscrim

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

comment:6 Changed 17 months ago by tscrim

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

Christian over my laptop concurs.

comment:7 Changed 17 months 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')

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

comment:8 Changed 17 months ago by chapoton

the branch is red..

comment:9 Changed 17 months ago by tscrim

  • Branch public/20484 deleted
  • Commit c9bdf03eb93aad748849c366229a2d4e610c90ce deleted

See comment:4

comment:10 Changed 8 months ago by embray

  • Resolution set to invalid
  • Status changed from positive_review to closed

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

Note: See TracTickets for help on using tickets.