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

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 tscrim

  • Branch set to public/combinat/speedup_coxeter_weyl_matrix_groups-19821
  • Commit set to 0b5fcec3ea079b5240414f4981bd860d7768b3c7
  • Status changed from new to needs_review

New commits:

0b4069cSpeedup has_right_descent() for Coxeter groups.
c2c3f17Speedup quantum_bruhat_graph by doing some things locally.
2b1a117Changed to avoid matrix constructor.
2426155Use a specialized version of GapElement.matrix() to avoid some overhead.
4caa2bfDon't store matrix() of Weyl group elements and some cleanup.
fcf0e35Added length cache to quantum_bruhat_graph().
0b5fcecGet a little more speed by using the matrices as keys for the length cache.

comment:2 Changed 3 years ago by tscrim

  • 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
Note: See TracTickets for help on using tickets.