Opened 3 years ago
Last modified 3 years ago
#19821 closed enhancement
Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph — at Version 2
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: | public/combinat/speedup_coxeter_weyl_matrix_groups-19821 (Commits) | Commit: | 0b5fcec3ea079b5240414f4981bd860d7768b3c7 |
Dependencies: | Stopgaps: |
Description (last modified by )
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.
This also includes a speedup of iterating over the entire Coxeter/Weyl? group.
Change History (2)
comment:1 Changed 3 years ago by
- Branch set to public/combinat/speedup_coxeter_weyl_matrix_groups-19821
- Commit set to 0b5fcec3ea079b5240414f4981bd860d7768b3c7
- Status changed from new to needs_review
comment:2 Changed 3 years ago by
- Cc darij chapoton stumpc5 added
- Description modified (diff)
Also, _finite_recognition
was no longer needed since we now have Coxeter types. One question I have for CoxeterGroup
is should the default ring for simply-laced types be ZZ
? The code which compares elements in the universal cyclotomic field to 0 is horribly slow and is the main reason why iteration over an instance of CoxeterGroup
(over the UCF) takes so long. Compare:
sage: WC = CoxeterGroup(['D',4], base_ring=ZZ) sage: %timeit L = [x for x in WC] 100 loops, best of 3: 12.1 ms per loop sage: WC = CoxeterGroup(['D',4]) # base_ring=UniversalCyclotomicField() sage: %timeit L = [x for x in WC] 1 loops, best of 3: 224 ms per loop sage: WC = CoxeterGroup(['D',5], base_ring=ZZ) sage: %timeit L = [x for x in WC] 10 loops, best of 3: 152 ms per loop sage: WC = CoxeterGroup(['D',5]) # base_ring=UniversalCyclotomicField() sage: %timeit L = [x for x in WC] 1 loops, best of 3: 3.97 s per loop
New commits:
Speedup has_right_descent() for Coxeter groups.
Speedup quantum_bruhat_graph by doing some things locally.
Changed libs.gap.element.GapElement.matrix() to avoid matrix constructor.
Use a specialized version of GapElement.matrix() to avoid some overhead.
Don't store matrix() of Weyl group elements and some cleanup.
Added length cache to quantum_bruhat_graph().
Get a little more speed by using the matrices as keys for the length cache.