Opened 11 years ago
Last modified 6 years ago
#9285 new enhancement
Challenge: iterating through E8 in 5 minutes
Reported by: | nthiery | Owned by: | sage-combinat |
---|---|---|---|
Priority: | major | Milestone: | sage-wishlist |
Component: | combinatorics | Keywords: | Coxeter groups, Chevie |
Cc: | sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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.
Change History (7)
comment:1 Changed 11 years ago by
- Description modified (diff)
comment:2 Changed 7 years ago by
- Description modified (diff)
comment:3 Changed 6 years ago by
comment:4 Changed 6 years ago by
- Description modified (diff)
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).
comment:5 Changed 6 years ago by
With the recent changes to #19821, I now get:
sage: sage: W = CoxeterGroup(['E',6], base_ring=ZZ) sage: sage: %time for x in W: pass CPU times: user 4.28 s, sys: 36.1 ms, total: 4.31 s Wall time: 4.23 s sage: sage: W = CoxeterGroup(['E',7], base_ring=ZZ) sage: %time for x in W: pass CPU times: user 4min 28s, sys: 20 ms, total: 4min 28s Wall time: 4min 28s
comment:6 Changed 6 years ago by
With #11187, on my laptop (see comment:4) I get
sage: W = ReflectionGroup(['E',8]) sage: %time for x in W.iteration('depth', False): pas CPU times: user 8min 44s, sys: 38.2 ms, total: 8min 44s Wall time: 8min 43s
There are a number of changes from #11187 (the cythonization) that could be lifted up to be used for the general Coxeter group iteration.
comment:7 Changed 6 years ago by
With Gap3 in Sage, it took 6m20s to go through E_{8} on my laptop (serially, comment:4):
gap> i:=0;; gap> W:=CoxeterGroup("E",7);; gap> ForEachElement(W,function(x)i:=i+1;end);
Instead of taking the nomenclature ["E",8], if we take Cartan matrix of E8 manually cm= CartanMatrix?([
R=RootSystem?(cm).root_lattice() alpha = R.simple_roots();alpha W = R.weyl_group(prefix="s") for w in W:
then we are able to act weyl group action on any element with a reasonable time. Although it is taking more time. it is not showing now error insufficient memory).