Opened 3 years ago

Last modified 3 years ago

#19821 closed enhancement

Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph — at Initial Version

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.2
Component: combinatorics Keywords: quantum bruhat graph
Cc: sage-combinat, aschilling, mshimo, nthiery, darij, chapoton, stumpc5, jipilab Merged in:
Authors: Travis Scrimshaw Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:


The primary goal of this ticket is to improve the creation speed for the quantum Bruhat graph. We do this in a number of ways:

  • Better management of data associated to lattice.nonparabolic_positive_roots.
  • Implement a (temporary) cache of the lengths of elements.

In addition, we also provide some general speedups to all matrix groups and Coxeter groups that came from looking into the above improvements. The net result is over 12x speedup of the creation of the quantum Bruhat graph:

sage: W = WeylGroup(['D',5], prefix='s')
sage: %time G = W.quantum_bruhat_graph()
CPU times: user 14 s, sys: 60.6 ms, total: 14 s
Wall time: 14 s

whereas previously this took over 3 minutes to compute. The downside is this has a larger memory footprint because of the temporary cache, but repeatedly computing the lengths of the elements was far too expensive.

Change History (0)

Note: See TracTickets for help on using tickets.