Opened 9 years ago

Last modified 3 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 tscrim)

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.

Change History (7)

comment:1 Changed 9 years ago by nthiery

  • Description modified (diff)

comment:2 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:3 Changed 4 years ago by bransingh

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).

Last edited 4 years ago by bransingh (previous) (diff)

comment:4 Changed 3 years ago by tscrim

  • 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 E8 is 240 times larger than E7, I expect it to take roughly 240 times longer (although from E6 to E7, 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 3 years ago by tscrim

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 3 years ago by tscrim

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 3 years ago by tscrim

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

gap> i:=0;;
gap> W:=CoxeterGroup("E",7);;
gap> ForEachElement(W,function(x)i:=i+1;end);
Note: See TracTickets for help on using tickets.