Changes between Initial Version and Version 2 of Ticket #19821


Ignore:
Timestamp:
01/02/16 09:31:53 (3 years ago)
Author:
tscrim
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

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #19821

    • Property Status changed from new to needs_review
    • Property Commit changed from to 0b5fcec3ea079b5240414f4981bd860d7768b3c7
    • Property Cc darij chapoton stumpc5 added
    • Property Branch changed from to public/combinat/speedup_coxeter_weyl_matrix_groups-19821
  • Ticket #19821 – Description

    initial v2  
    1212}}}
    1313whereas 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.
     14
     15This also includes a speedup of iterating over the entire Coxeter/Weyl group.