Opened 6 years ago

Closed 3 years ago

#20445 closed enhancement (fixed)

Iteration through finite Coxeter groups

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-8.3
Component: combinatorics Keywords:
Cc: tscrim, chapoton, nthiery, vripoll Merged in:
Authors: Travis Scrimshaw, Christian Stump Reviewers: Christian Stump, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: d3ef5a8 (Commits, GitHub, GitLab) Commit: d3ef5a848c90cd0fba80b0fe61f48d2693f9ea5b
Dependencies: Stopgaps:

Status badges

Description (last modified by stumpc5)

The algorithm in chevie is very different from the algorithm we currently have:

ForEachElement:=function(W,f)local l,g;
  if not IsFinite(W) then Error("only for finite Coxeter groups");
  elif W.nbGeneratingReflections=0 then f(W.identity);return;
  fi;
  l:=List([0..W.nbGeneratingReflections],i->
        ReflectionSubgroup(W,W.reflectionsLabels{[1..i]}));
  l:=List([1..Length(l)-1],i->ReducedRightCosetRepresentatives(l[i+1],l[i]));
  g:=function(x,v)local y;
    if Length(v)=0 then f(x);
    else for y in v[1] do g(x*y,v{[2..Length(v)]});od;
    fi;
  end;
  g(W.identity,l);
end;

We should also implement that algorithm (maybe even with hard-coded coset representatives in the finite case) so that we can see if this is indeed faster.

The two needed methods are

#############################################################################
##
#F  ReducedInRightCoset( <W> , <w> )  . . . . . reduced element in coset W.w
##
##  w is an automorphism of a parent Coxeter group of W.
##  'ReducedInRightCoset' returns the unique element in the right
##  coset W.w which is W-reduced.
##

AbsCoxOps.ReducedInRightCoset:=function(W,w)local i;
  while true  do
    i := FirstLeftDescending(W, w);
    if i=false then return w; fi;
    w := W.reflections[i] * w;
  od;
end;

#############################################################################
##
#F  ReducedRightCosetRepresentatives( <W>, <H> )  . . . . . . . . . . . . .
#F  . . . . . . . . . . . . . . .  distinguished right coset representatives
##
##  'ReducedRightCosetRepresentatives'  returns a list of reduced words in the
##  Coxeter group <W> that are distinguished right  coset representatives for
##  the right cosets H\W where  H is a reflection subgroup  of W.
##
ReducedRightCosetRepresentatives:=function(W, H)local res, totest, new;
  totest:=Set([W.identity]);
  res:=Set([W.identity]);
  repeat
    new:=Concatenation(List(totest,w->List(
      W.reflections{W.generatingReflections},s->ReducedInRightCoset(H, w*s))));
    UniteSet(res,totest);
    totest:=Difference(new,res);
  until Length(totest)=0;
  InfoChevie2("#I nb. of cosets: ",Length(res),"\n");
  SortBy(res,x->CoxeterLength(W,x));
  return res;
end;

Change History (40)

comment:1 Changed 6 years ago by stumpc5

  • Description modified (diff)

comment:2 Changed 6 years ago by stumpc5

###########################################################################
#
# N.B. a difference with older versions of Chevie is that IsLeftDescending and
# FirstLeftDescending  return  an  index  in  the  list  of  generators, not a
# reflectionName,  for  efficiency.  LeftDescentSet  still  returns  names  of
# reflections.
#
###########################################################################

##  generic reduction of FirstLeftDescending to IsLeftDescending
##  in practical implementations of Coxeter groups this routine can often
##  be overriden by a more efficient one.

AbsCoxOps.FirstLeftDescending:=function(W, x)local i,ILD;
  ILD:=W.operations.IsLeftDescending; # avoid dispatching overhead
  for i in W.generatingReflections do if ILD(W,x,i) then return i; fi; od;
  return false;
end;

comment:3 Changed 6 years ago by stumpc5

  • Branch set to u/stumpc5/20445

comment:4 Changed 6 years ago by git

  • Commit set to 3d5bd19b3628eccdad189d2eb6db08a89295cab0

Branch pushed to git repo; I updated commit sha1. New commits:

a2ef2e4added a few sentences to the doc
dc01066started to add 'optional - gap3'
fd0c9ccadded optional gap3
1537a79added optional gap3
60acebcMerge branch 'u/stumpc5/11187' into u/stumpc5/20445
3d5bd19first version of the algorithm in chevie

comment:5 Changed 6 years ago by stumpc5

  • Summary changed from Iteration through Coxeter groups to Iteration through finite Coxeter groups

Last 10 new commits:

8810c41fixed one doctest + work on the invariant form
2ba3740fixed another doctest + a typo
e28bbecedited the length function to always use the reduced word
8f79ffajust playing with first methods
a2ef2e4added a few sentences to the doc
dc01066started to add 'optional - gap3'
fd0c9ccadded optional gap3
1537a79added optional gap3
60acebcMerge branch 'u/stumpc5/11187' into u/stumpc5/20445
3d5bd19first version of the algorithm in chevie

comment:6 Changed 6 years ago by stumpc5

Travis, I implemented a first version of the algoritm, getting all needed cosets in E7 takes 2/3 of our iteration time, but constructing the elements in the end takes about 30secs. If you find the time, I am sure you see how to speed the algorithm. The function is parabolic_iteration.

comment:7 Changed 6 years ago by git

  • Commit changed from 3d5bd19b3628eccdad189d2eb6db08a89295cab0 to eb75f71f18ff6faf5a3d2436caa691d74bdc460d

Branch pushed to git repo; I updated commit sha1. New commits:

a60cf31added some missing optional gap3
aaf59b1Merge branch 'u/stumpc5/11187' into u/stumpc5/20445
eb75f71turned it into an iterator to make every product only once. somhow results in infinite iteration

comment:8 Changed 6 years ago by git

  • Commit changed from eb75f71f18ff6faf5a3d2436caa691d74bdc460d to 26d89e25c84a7c569fe0cffae8ec457baf3e3e67

Branch pushed to git repo; I updated commit sha1. New commits:

feebf97finalized the invariant form
4955d68added the missing optional gap3 in the cython file
c5c43bcthe next round of optional gap3 insertions
6d788c9Merge branch 'u/stumpc5/11187' into u/stumpc5/20445
26d89e2- made the computation of reduced_coset_repesentatives really fast ~0.1sec in E8

comment:9 Changed 6 years ago by git

  • Commit changed from 26d89e25c84a7c569fe0cffae8ec457baf3e3e67 to e7eb93cc439710460b9be384cfb47ae63188d5c7

Branch pushed to git repo; I updated commit sha1. New commits:

e7eb93cpushed a new version of the parabolic algorithm that is 30% faster than ours

comment:10 Changed 6 years ago by stumpc5

sage: timeit("for w in W.iteration('depth',False): pass",number=5)
5 loops, best of 3: 6.33 s per loop
sage: from sage.combinat.root_system.reflection_group_c import parabolic_iteration
sage: timeit("for w in parabolic_iteration(W): pass",number=5)    
5 loops, best of 3: 4.28 s per loop

Okay, I can now get down quite a bit from our last weeks algorithm. Drawback is that it needs quite some memory (for E8, we have to keep E7 in memory). I provide an alternative in which order the parabolic is computed, but that doesn't seem to speed the computation.

  • If @tscrim looks at the code and improves it further, we might beat the 5 minutes for E8!
  • The code can also perfectly be paralellized!
Last edited 6 years ago by stumpc5 (previous) (diff)

comment:11 Changed 6 years ago by git

  • Commit changed from e7eb93cc439710460b9be384cfb47ae63188d5c7 to 7eebd4b5cdecf9263eff38253b16d8ca9d777a3c

Branch pushed to git repo; I updated commit sha1. New commits:

7eebd4bminor tweak

comment:12 Changed 6 years ago by stumpc5

I locally reimplemented the multiplication of PermutationGroupElement. This resulted in

sage: W = ReflectionGroup(['E',7])                                                
sage: from sage.combinat.root_system.reflection_group_c import parabolic_iteration
sage: timeit("for w in parabolic_iteration(W): pass",number=5)                    
5 loops, best of 3: 2.4 s per loop

If we provide a very restricted implementation of permutations ourselves, we might get down further quite a bit. Remark: the algorithm without the multiplication and creation of new permutation group elements only takes .5sec, so there is a lot to improve still.

comment:13 Changed 6 years ago by git

  • Commit changed from 7eebd4b5cdecf9263eff38253b16d8ca9d777a3c to 88ec6a0d7a77fe89034218fb05a328de8fbfaa37

Branch pushed to git repo; I updated commit sha1. New commits:

88ec6a0implemented a local perm grp elt multiplication

comment:14 Changed 5 years ago by stumpc5

I just redid the computations and it seems to be about twice as fast as in gap3:

sage: W = ReflectionGroup(['E',7])
sage: from sage.combinat.root_system.reflection_group_c import parabolic_iteration
sage: timeit("for w in parabolic_iteration(W): pass",number=5)
5 loops, best of 3: 1.56 s per loop
sage: timeit("for w in parabolic_iteration(W): pass",number=5)
5 loops, best of 3: 1.43 s per loop
sage: W = ReflectionGroup(['E',8])
sage: %time for w in parabolic_iteration(W): pass

CPU times: user 9min 12s, sys: 3.81 s, total: 9min 16s
Wall time: 9min 16s

So we are slowly approaching the 5min...

comment:15 follow-up: Changed 5 years ago by tscrim

Took 3.5Gb of RAM with this ticket, but on my laptop, this is what I got:

sage: W = ReflectionGroup(['E',8])
sage: from sage.combinat.root_system.reflection_group_c import parabolic_iteration
sage: %time for w in parabolic_iteration(W): pass
CPU times: user 4min 23s, sys: 604 ms, total: 4min 23s
Wall time: 4min 23s

comment:16 Changed 5 years ago by git

  • Commit changed from 88ec6a0d7a77fe89034218fb05a328de8fbfaa37 to bc3c926b27ccca4371b28a4dbac0169d639ff191

Branch pushed to git repo; I updated commit sha1. New commits:

244e6ffMerge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
f541349Some last little beautification.
bc3c926Merge branch 'u/stumpc5/11187' into u/stumpc5/20445

comment:17 in reply to: ↑ 15 ; follow-up: Changed 5 years ago by stumpc5

Replying to tscrim:

CPU times: user 4min 23s, sys: 604 ms, total: 4min 23s Wall time: 4min 23s

Great, I believe you can claim to be the first person ever who iterated through E8 in less than 5 minutes! (I was expecting that since 1. your computer was about twice as fast as mine last week, and 2. you took ~8 minutes to iter through E8 in chevie, and my code is about twice as fast as the chevie code.)

  1. I would really like to see how to implement our own permutation group elements with only what we need. I would hope that to again result in some speedup. One question there: we have w(-\beta) = -w(\beta), so we would not need to record the complete permutation on all roots, but on the positive roots would be enough. That would speed several computations such as creating new elements and testing for equality), but it would have the drawback that we constantly need to work mod N (N=nr of positive roots), e.g., we would have such checks and mod's when multiplying two permutations.
  1. We should get your parallelization to work with this so that people can then use many cores to actually do stuff with the elements in type E8.
Last edited 5 years ago by nthiery (previous) (diff)

comment:18 Changed 5 years ago by git

  • Commit changed from bc3c926b27ccca4371b28a4dbac0169d639ff191 to e7408933724f8453cd0ec1bc3ed9c73fac403c4a

Branch pushed to git repo; I updated commit sha1. New commits:

0db28d6fixed doctests that have not been run last week!
7afc02cFixing doctests in combinat/root_system/coxeter_group.py.
0269425Blanket fix bare except block.
9b0ef92Making it an AttributeError.
0985005Merge branch 'public/11187' into u/stumpc5/20445
e740893uses the local multiplication now also in the other iterator

comment:19 Changed 5 years ago by stumpc5

Travis, could you also now run

sage: W = ReflectionGroup(['E',8])
sage: %time for w in W.iteration("depth",False): pass

It now also uses the local multiplication, so it should also speed quite a bit. On my machine, it's only 1.5 times as slow.

comment:20 Changed 5 years ago by tscrim

With doing other things on my laptop:

sage: W = ReflectionGroup(['E',8])
sage: %time for w in W.iteration("depth",False): pass
CPU times: user 6min 39s, sys: 22.5 ms, total: 6min 39s
Wall time: 6min 39s

comment:21 Changed 5 years ago by git

  • Commit changed from e7408933724f8453cd0ec1bc3ed9c73fac403c4a to abfff5ffdf5e3d7a90bdaa542ecca3ba2691bffe

Branch pushed to git repo; I updated commit sha1. New commits:

3e25053Merge branch 'public/11187' into u/stumpc5/20445
abfff5fMerge branch 'develop' into u/stumpc5/20445

comment:22 follow-up: Changed 5 years ago by stumpc5

@Nicolas: I just now see that you (I think) accidentally edited my comment (comment 5 above from here) instead of replying three weeks ago. Could you quickly recheck?

comment:23 in reply to: ↑ 17 ; follow-up: Changed 5 years ago by nthiery

Replying to stumpc5:

  1. I would really like to see how to implement our own permutation group elements with only what we need. I would hope that to again result in some speedup. One question there: we have w(-\beta) = -w(\beta), so we would not need to record the complete permutation on all roots, but on the positive roots would be enough. That would speed several computations such as creating new elements and testing for equality), but it would have the drawback that we constantly need to work mod N (N=nr of positive roots), e.g., we would have such checks and mod's when multiplying two permutations.

This business sounds of the same nature as what we have for affine permutations (in window notation). Would there be a way to use the same implementation behind the scene?

Cheers,

Nicolas

comment:24 in reply to: ↑ 22 Changed 5 years ago by nthiery

Replying to stumpc5:

@Nicolas: I just now see that you (I think) accidentally edited my comment (comment 5 above from here) instead of replying three weeks ago. Could you quickly recheck?

Oops, reverted!

comment:25 in reply to: ↑ 23 ; follow-up: Changed 5 years ago by stumpc5

Replying to nthiery:

Replying to stumpc5: This business sounds of the same nature as what we have for affine permutations (in window notation). Would there be a way to use the same implementation behind the scene?

And also with colored permutations, isn't it? The main difference is that here (and also in signed permutations) one works mod N, for colored permutations one works "+N mod kN", and for affine permutation one does not work mod anything.

I would propose to first work out the implementation here and then see if we can use it also in the other places. I only don't see how to actually do the implementation in an optimal way, so some support of yours and/or Travis is appreciated.

Some concrete questions:

  1. It seems that we should use the same data structure as for PermutationGroupElement:
        self.perm = <int *>sig_malloc(sizeof(int) * self.N)
    
    Do you agree? Can we even get anything significantly better than sticking to PermutationGroupElement if we do it ourselves? This also asks whether we can do better when multiplying elements, I do not see what
     cdef PermutationGroupElement prod = PermutationGroupElement.__new__(PermutationGroupElement)
    
    does or how long it takes, see the method _new_mul_ in reflection_group_c.pyx.
  1. It seems that we are using PermutationGroupElement in a few places (when talking to GAP3}), but this might just be that we need the cycle string representation for that.

comment:26 Changed 5 years ago by stumpc5

@Travis: Could you have a brief look at the _new_mul_ in reflection_group_c.pyx to check whether I am missing something, or whether I could use that as a first improvement in this algorithm.

I indeed plan to have this ticket only contain the improvements for now (then having plenty of options for iterating through finite Coxeter groups), postponing the work and testing for a new data structure to a new ticket.

comment:27 in reply to: ↑ 25 ; follow-ups: Changed 5 years ago by tscrim

Replying to stumpc5:

I would propose to first work out the implementation here and then see if we can use it also in the other places. I only don't see how to actually do the implementation in an optimal way, so some support of yours and/or Travis is appreciated.

I'm really starting to consider that what we should do is create our own separate project where we write all of this independently (in, say, C/C++). At this stage, I'm somewhat concerned with the additional overhead that Cython could impose and the lack of complete memory control. Although I cannot commit serious time to working on this for then next two weeks (I will be in grading and math mode). Over the summer starting in June, I should be able to do so.

Some concrete questions:

  1. It seems that we should use the same data structure as for PermutationGroupElement:
        self.perm = <int *>sig_malloc(sizeof(int) * self.N)
    
    Do you agree? Can we even get anything significantly better than sticking to PermutationGroupElement if we do it ourselves?

I think we can avoid a bit of overhead of maintaining the GAP and category information. Although it is hard to tell how much of an impact this will have on things.

This also asks whether we can do better when multiplying elements, I do not see what

 cdef PermutationGroupElement prod = PermutationGroupElement.__new__(PermutationGroupElement)

does or how long it takes, see the method _new_mul_ in reflection_group_c.pyx.

This creates a new element in memory, but it does not call the __init__. It is essential and done in Python kernel, so we won't get any better.

  1. It seems that we are using PermutationGroupElement in a few places (when talking to GAP3}), but this might just be that we need the cycle string representation for that.

GAP4 doesn't store things as cycle strings AFAIK, and so I doubt GAP3 does either.Replying to stumpc5:

I would propose to first work out the implementation here and then see if we can use it also in the other places. I only don't see how to actually do the implementation in an optimal way, so some support of yours and/or Travis is appreciated.

I'm really starting to consider that what we should do is create our own separate project where we write all of this independently (in, say, C/C++). At this stage, I'm somewhat concerned with the additional overhead that Cython could impose and the lack of complete memory control. Although I cannot commit serious time to working on this for then next two weeks (I will be in grading and math mode). Over the summer starting in June, I should be able to do so.

Some concrete questions:

  1. It seems that we should use the same data structure as for PermutationGroupElement:
        self.perm = <int *>sig_malloc(sizeof(int) * self.N)
    
    Do you agree? Can we even get anything significantly better than sticking to PermutationGroupElement if we do it ourselves?

I think we can avoid a bit of overhead of maintaining the GAP and category information. Although it is hard to tell how much of an impact this will have on things.

This also asks whether we can do better when multiplying elements, I do not see what

 cdef PermutationGroupElement prod = PermutationGroupElement.__new__(PermutationGroupElement)

does or how long it takes, see the method _new_mul_ in reflection_group_c.pyx.

This creates a new element in memory, but it does not call the __init__. It is essential and done in Python kernel, so we won't get any better.

  1. It seems that we are using PermutationGroupElement in a few places (when talking to GAP3}), but this might just be that we need the cycle string representation for that.

GAP4 doesn't store things as cycle strings AFAIK, and so I doubt GAP3 does either. We could very likely replace these calls with something better (if we are calling GAP3).

Last edited 5 years ago by tscrim (previous) (diff)

comment:28 in reply to: ↑ 27 Changed 5 years ago by stumpc5

Replying to tscrim:

Replying to stumpc5: I'm really starting to consider that what we should do is create our own separate project where we write all of this independently (in, say, C/C++). At this stage, I'm somewhat concerned with the additional overhead that Cython could impose and the lack of complete memory control. Although I cannot commit serious time to working on this for then next two weeks (I will be in grading and math mode). Over the summer starting in June, I should be able to do so.

Let me quickly ask: by "create our own separate project where we write all of this independently (in, say, C/C++)" you mean implementing this permutation group element there and then use it from our sage implementation, right?

I'd be happy to follow and help with than whenever you find the time, but at first I will likely only be watching you doing it...

comment:29 in reply to: ↑ 27 ; follow-up: Changed 5 years ago by nthiery

Replying to tscrim:

I'm really starting to consider that what we should do is create our own separate project where we write all of this independently (in, say, C/C++). At this stage, I'm somewhat concerned with the additional overhead that Cython could impose and the lack of complete memory control. Although I cannot commit serious time to working on this for then next two weeks (I will be in grading and math mode). Over the summer starting in June, I should be able to do so.

We can discuss this in Meudon.

I think we can avoid a bit of overhead of maintaining the GAP and category information. Although it is hard to tell how much of an impact this will have on things.

For the record: I just checked, and the data structure for permutation group elements is just a reference to the parent and a C-list of ints; plus a few slots which are unused by default (e.g. a reference to a gap element). So the only overhead is copying over the reference to the parent, and a bit of extra memory allocation

Of course, the parent itself has stuff about GAP and categories, but that's initialized once for all, and does not influence arithmetic on elements.

Cheers,

Nicolas

comment:30 in reply to: ↑ 29 Changed 5 years ago by tscrim

Replying to nthiery:

Replying to tscrim:

I'm really starting to consider that what we should do is create our own separate project where we write all of this independently (in, say, C/C++). At this stage, I'm somewhat concerned with the additional overhead that Cython could impose and the lack of complete memory control. Although I cannot commit serious time to working on this for then next two weeks (I will be in grading and math mode). Over the summer starting in June, I should be able to do so.

We can discuss this in Meudon.

Sounds good.

I think we can avoid a bit of overhead of maintaining the GAP and category information. Although it is hard to tell how much of an impact this will have on things.

For the record: I just checked, and the data structure for permutation group elements is just a reference to the parent and a C-list of ints; plus a few slots which are unused by default (e.g. a reference to a gap element). So the only overhead is copying over the reference to the parent, and a bit of extra memory allocation

Of course, the parent itself has stuff about GAP and categories, but that's initialized once for all, and does not influence arithmetic on elements.

I am partially worried about how much these extra copy operations cost on the E8 iteration scale, as well as the inherent overhead of the generated code from Cython. Plus I like having code where we completely control the memory allocations. It might end up that we really don't see much of an improvement, but I think it is worth trying.

comment:31 Changed 3 years ago by tscrim

  • Branch changed from u/stumpc5/20445 to public/combinat/finite_coxeter_iteration-20445
  • Commit changed from abfff5ffdf5e3d7a90bdaa542ecca3ba2691bffe to 111d92a26b5d12d7ebaf1c323275326aa24c0318
  • Milestone changed from sage-7.2 to sage-8.3

New commits:

7b8b94bMerge branch 'develop' into u/stumpc5/20445
2cef8bfMerge branch 'develop' into u/stumpc5/20445
111d92aMerge branch 'u/stumpc5/20445' of trac.sagemath.org:sage into public/combinat/finite_coxeter_iteration-20445

comment:32 Changed 3 years ago by git

  • Commit changed from 111d92a26b5d12d7ebaf1c323275326aa24c0318 to f061066b8e9338f224de6ab9770d119446744704

Branch pushed to git repo; I updated commit sha1. New commits:

f061066Doing some cleanup and now ready for review.

comment:33 Changed 3 years ago by tscrim

  • Authors set to Travis Scrimshaw, Christian Stump
  • Reviewers set to Christian Stump, Travis Scrimshaw
  • Status changed from new to needs_review

comment:34 Changed 3 years ago by chapoton

some failing doctests, missing optional gap3

comment:35 Changed 3 years ago by git

  • Commit changed from f061066b8e9338f224de6ab9770d119446744704 to 06e5a466d419de10227f82c5157abf7c1d059c26

Branch pushed to git repo; I updated commit sha1. New commits:

06e5a46Fixing doctests.

comment:36 Changed 3 years ago by tscrim

Fixed.

comment:37 Changed 3 years ago by git

  • Commit changed from 06e5a466d419de10227f82c5157abf7c1d059c26 to 348ece0da4f7c7530e1789ac6a42c696cb69b449

Branch pushed to git repo; I updated commit sha1. New commits:

d622df2started the discriminant of a reflection group
3d4f036implemented the discriminant up- and downstairs
1c82a89Merge branch 'public/combinat/finite_coxeter_iteration-20445' of git://trac.sagemath.org/sage into 20445
348ece0removed a few comments

comment:38 Changed 3 years ago by git

  • Commit changed from 348ece0da4f7c7530e1789ac6a42c696cb69b449 to d3ef5a848c90cd0fba80b0fe61f48d2693f9ea5b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d3ef5a8removed a few comments

comment:39 Changed 3 years ago by stumpc5

  • Status changed from needs_review to positive_review

looked through Travis' changes...

comment:40 Changed 3 years ago by vbraun

  • Branch changed from public/combinat/finite_coxeter_iteration-20445 to d3ef5a848c90cd0fba80b0fe61f48d2693f9ea5b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.