#9285: Challenge: iterating through E8 in 5 minutes
------------------------------------------+-----------------------------
Reporter: nthiery | Owner: sage-combinat
Type: enhancement | Status: new
Priority: major | Milestone: sage-wishlist
Component: combinatorics | Resolution:
Keywords: Coxeter groups, Chevie | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------------------+-----------------------------
Old description:
> The current code for iterating trough all elements of a Coxeter group
> is currently ridiculously slow. For E8, it should take no more than a
> couple minutes as Franck Lubeck's reported was possible in GAP. The
> goal is not to brag, but to make sure that the infrastructure does not
> impose unnecessary overhead.
>
> There are several routes to this end, which all deserve to be explored:
>
> * Using GAP's code; this will require at least fixing a {{{select}}}
> issue in GAP's interface (TODO: add ticket), if not using libGAP,
> and implementing the iter protocol for gap objects using GAP's
> Iterator (TODO: add ticket).
>
> Update (09/2014): for finite groups of size>1000, Sage's iterator
> for matrix groups now asks GAP to make the group into a permutation
> group, and asks GAP for an iterator thereupon through
> libgap. However, for E8, this still can lead to overflowing GAP's
> workspace. To be investigated.
>
> * Optimizing the underlying CombinatorialFreeModule's arithmetic
> * Ensuring that the permutation arithmetic is as fast as it should be
> * Optimizing the generic Coxeter group code
> * Using properly Coxeter 3.
>
> This is fast for small groups, but uses up memory for E8 on my
> machine:
>
> {{{
> sage: W = CoxeterGroup(["E",6], implementation="coxeter3")
> sage: %time for w in CoxeterGroups().parent_class.__iter__(W): pass #
> generic iterator
> CPU times: user 31.1 s, sys: 31.4 ms, total: 31.1 s
> Wall time: 31.1 s
>
> sage: %time for w in W: pass #
> Coxeter3's iterator
> CPU times: user 1.61 s, sys: 24.1 ms, total: 1.63 s
> Wall time: 1.61 s
>
> sage: W = CoxeterGroup(["E",7], implementation="coxeter3")
> sage: %time for w in W: pass
> CPU times: user 1min 33s, sys: 336 ms, total: 1min 33s
> Wall time: 1min 33s
>
> sage: W = CoxeterGroup(["E",8], implementation="coxeter3")
> sage: %time for w in W: pass
> sorry, insufficient memory
> }}}
>
> To be investigated, but Coxeter3 probably builds the full group in
> memory.
New description:
The current code for iterating trough all elements of a Coxeter group
is currently ridiculously slow. For E,,8,,, it should take no more than a
couple minutes as Franck Lubeck's reported was possible in GAP. The
goal is not to brag, but to make sure that the infrastructure does not
impose unnecessary overhead.
There are several routes to this end, which all deserve to be explored:
* Using GAP's code; this will require at least fixing a {{{select}}}
issue in GAP's interface (TODO: add ticket), if not using libGAP,
and implementing the iter protocol for gap objects using GAP's
Iterator (TODO: add ticket).
Update (09/2014): for finite groups of size>1000, Sage's iterator
for matrix groups now asks GAP to make the group into a permutation
group, and asks GAP for an iterator thereupon through
libgap. However, for E8, this still can lead to overflowing GAP's
workspace. To be investigated.
* Optimizing the underlying CombinatorialFreeModule's arithmetic
* Ensuring that the permutation arithmetic is as fast as it should be
* Optimizing the generic Coxeter group code
* Using properly Coxeter 3.
This is fast for small groups, but uses up memory for E8 on my
machine:
{{{
sage: W = CoxeterGroup(["E",6], implementation="coxeter3")
sage: %time for w in CoxeterGroups().parent_class.__iter__(W): pass #
generic iterator
CPU times: user 31.1 s, sys: 31.4 ms, total: 31.1 s
Wall time: 31.1 s
sage: %time for w in W: pass #
Coxeter3's iterator
CPU times: user 1.61 s, sys: 24.1 ms, total: 1.63 s
Wall time: 1.61 s
sage: W = CoxeterGroup(["E",7], implementation="coxeter3")
sage: %time for w in W: pass
CPU times: user 1min 33s, sys: 336 ms, total: 1min 33s
Wall time: 1min 33s
sage: W = CoxeterGroup(["E",8], implementation="coxeter3")
sage: %time for w in W: pass
sorry, insufficient memory
}}}
To be investigated, but Coxeter3 probably builds the full group in
memory.
--
Comment (by tscrim):
On my Asus with i7 quad-core (hyperthreaded to 8) and 8GB RAM and #19821
(and doing other things), I get the following running serially (on 1
thread):
{{{
sage: W = CoxeterGroup(['E',6], base_ring=ZZ)
sage: %time for x in W: pass
CPU times: user 11.2 s, sys: 32 ms, total: 11.2 s
Wall time: 11.2 s
sage: W = CoxeterGroup(['E',7], base_ring=ZZ)
sage: %time for x in W: pass
CPU times: user 5min 47s, sys: 14.4 ms, total: 5min 47s
Wall time: 5min 46s
}}}
Since E,,8,, is 240 times larger than E,,7,,, I expect it to take roughly
240 times longer (although from E,,6,, to E,,7,,, it only took 31x longer
whereas there is a 56x size difference). That is roughly 23 hours... (in
reality, it is probably a lot less, but still on the order of hours).
--
Ticket URL: <http://trac.sagemath.org/ticket/9285#comment:4>
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.
