#19821: Increase speed for Coxeter groups, Weyl groups, and quantum Bruhat graph
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.0
Component: combinatorics | Resolution:
Keywords: quantum bruhat | Merged in:
graph | Reviewers:
Authors: Travis Scrimshaw | Work issues:
Report Upstream: N/A | Commit:
Branch: | 0b5fcec3ea079b5240414f4981bd860d7768b3c7
public/combinat/speedup_coxeter_weyl_matrix_groups-19821| Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by tscrim):
* cc: darij, chapoton, stumpc5 (added)
Old 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.
New 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.
This also includes a speedup of iterating over the entire Coxeter/Weyl
group.
--
Comment:
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
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/19821#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
