Challenge: iterating through E8 in 5 minutes

[nthiery]

The current code for iterating trough all elements of a Coxeter group
is currently ridiculously slow. For E₈, 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.

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: Coxeter groups, Chevie

Issue created by migration from https://trac.sagemath.org/ticket/9285

[sagetrac-bransingh]

comment:3

Instead of taking the nomenclature ["E",8], if we take Cartan matrix of E8 manually
cm= CartanMatrix([
[2,-1,0,0,0,0,0,0],
[-1,2,-1,0,0,0,0,0],
[0,-1,2,-1,0,0,0,0],
[0,0,-1,2,-1,0,0,0],
[0,0,0,-1,2,-1,0,-1],
[0,0,0,0,-1,2,-1,0],
[0,0,0,0,0,-1,2,0],
[0,0,0,0,-1,0,0,2]],cartan_type_check = False);cm
R=RootSystem(cm).root_lattice()
alpha = R.simple_roots();alpha
W = R.weyl_group(prefix="s")
for w in W:
w.action(alpha[2]) ==alpha[4] :
print 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).

[tscrim]

comment:4

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₈ is 240 times larger than E₇, I expect it to take roughly 240 times longer (although from E₆ to E₇, 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).

[tscrim]

comment:5

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

[tscrim]

comment:6

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.

[tscrim]

comment:7

With Gap3 in Sage, it took 6m20s to go through E₈ on my laptop (serially, comment:4):

gap> i:=0;;
gap> W:=CoxeterGroup("E",7);;
gap> ForEachElement(W,function(x)i:=i+1;end);