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: |

### Description

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.

**Note:**See TracTickets for help on using tickets.