Opened 3 years ago
Closed 3 years ago
#25485 closed enhancement (fixed)
reduced words in coxeter groups
Reported by:  stumpc5  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  combinatorics  Keywords:  coxeter group, days93.51 
Cc:  tscrim, jmichel, tdouvropoulos, zabrocki, aschilling  Merged in:  
Authors:  Christian Stump  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  b4ebf17 (Commits, GitHub, GitLab)  Commit:  b4ebf17b588dbc1e7fedd038e3ca526fcb6a2785 
Dependencies:  Stopgaps: 
Description (last modified by )
Implement the braid orbit of a reduced word (and thus all reduced words) in a Coxeter group
Change History (38)
comment:1 Changed 3 years ago by
 Branch set to u/stumpc5/reduced_words_in_coxeter_groups
comment:2 Changed 3 years ago by
 Commit set to 4736a75c29adac4349f7c4c63375367e84f2155e
comment:3 Changed 3 years ago by
 Cc tscrim jmichel tdouvropoulos added
 Component changed from PLEASE CHANGE to combinatorics
 Description modified (diff)
 Keywords coxeter group days93.51 added
 Status changed from new to needs_review
 Type changed from PLEASE CHANGE to enhancement
have to add some doctests still.
Q: leave the old implementation or not?
comment:4 Changed 3 years ago by
 Commit changed from 4736a75c29adac4349f7c4c63375367e84f2155e to e8ed32b4a2e570f44fa8abaf8286262f9e5d8e07
Branch pushed to git repo; I updated commit sha1. New commits:
e8ed32b  added documentation

comment:5 Changed 3 years ago by
 Commit changed from e8ed32b4a2e570f44fa8abaf8286262f9e5d8e07 to 7c55fab75053432140611e4f10a8c06abad8f05b
Branch pushed to git repo; I updated commit sha1. New commits:
7c55fab  removed commented old method

comment:6 Changed 3 years ago by
okay, now ready for review
comment:7 Changed 3 years ago by
 Commit changed from 7c55fab75053432140611e4f10a8c06abad8f05b to 310c0bee592bb64622914e8030474864ead18329
comment:8 Changed 3 years ago by
Old:
sage: W = WeylGroup(['A',4]) sage: w0 = WeylGroup(['A',4]).long_element() sage: %time len(w0.reduced_words()) CPU times: user 1.78 s, sys: 17.4 ms, total: 1.8 s Wall time: 1.76 s 768
Current branch:
sage: %time len(w0.reduced_words()) CPU times: user 7.36 ms, sys: 0 ns, total: 7.36 ms Wall time: 7.19 ms 768
comment:9 Changed 3 years ago by
 Branch changed from u/stumpc5/reduced_words_in_coxeter_groups to public/combinat/reduced_words_coxeter_groups25485
 Commit changed from 310c0bee592bb64622914e8030474864ead18329 to 5b670a59b4ad75a23b6a2b8bec659e0c1d71cd3e
 Reviewers set to Travis Scrimshaw
comment:10 Changed 3 years ago by
 Commit changed from 5b670a59b4ad75a23b6a2b8bec659e0c1d71cd3e to 4de48f57af5980b4af33ca6a5e6302aa77d50b40
comment:11 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:12 Changed 3 years ago by
 Status changed from positive_review to needs_work
Failing doctests. Currently fixing.
comment:13 Changed 3 years ago by
 Commit changed from 4de48f57af5980b4af33ca6a5e6302aa77d50b40 to 188c6b11aa732cb8b368ad2574142e4ec79bd566
Branch pushed to git repo; I updated commit sha1. New commits:
188c6b1  Fixing doctest failures.

comment:14 followup: ↓ 15 Changed 3 years ago by
 Cc zabrocki aschilling added
 Status changed from needs_work to needs_review
Mike, Anne, I put you in cc because I had to change one of the kSchur function book tests.
comment:15 in reply to: ↑ 14 ; followup: ↓ 16 Changed 3 years ago by
Replying to tscrim:
Mike, Anne, I put you in cc because I had to change one of the kSchur function book tests.
It only changes the order of the output, right? I guess that is ok.
comment:16 in reply to: ↑ 15 Changed 3 years ago by
Replying to aschilling:
Replying to tscrim:
Mike, Anne, I put you in cc because I had to change one of the kSchur function book tests.
It only changes the order of the output, right? I guess that is ok.
It also is now a list of tuples whereas before it was a list of lists. (The sorted
is because the new algorithm does not have any promises of a consistent output order.)
comment:17 Changed 3 years ago by
Is the tuple output necessary for the speed improvement? If so, I would say it can be justified. Otherwise I don't think its a good idea to change the output type where it isn't necessary.
comment:18 Changed 3 years ago by
Is the tuple output necessary for the speed improvement? If so, I would say it can be justified. Otherwise I don't think its a good idea to change the output type where it isn't necessary.
Yes it is in the following sense. The new algorithm is as follows: take any tuple of integers (a reduced word) and a list of homogeneous replacement rules (braid relations, homogeneous meaning that the replacements do not change length), the algorithms is a brute force computation of this orbit by collecting new tuples into a set to be checked against. (The algorithm can actually be used without reference to reduced words or braid relations.)
So we do need to use tuples for hashing.
comment:19 Changed 3 years ago by
Is there significant loss of speed by replacing the line
return list(BraidOrbit(word, self.parent().braid_relations()))
by
return [list(w) for w in BraidOrbit(word, self.parent().braid_relations())]
?
comment:20 Changed 3 years ago by
sage: W = CoxeterGroup(['A',5]) sage: w = W.long_element() sage: %time len(w.reduced_words()) CPU times: user 1.43 s, sys: 0 ns, total: 1.43 s Wall time: 1.43 s 292864 sage: %time len([ list(rw) for rw in w.reduced_words()]) CPU times: user 1.92 s, sys: 44.4 ms, total: 1.97 s Wall time: 1.93 s 292864
comment:21 Changed 3 years ago by
I somewhat agree that it is weird that reduced_word
outputs a list while reduced_words
outputs tuples.
On the other hand, it seems to me that tuples would be more reasonable altogether because a reduced word is something that "cannot be changed by hand". But I also see that the list
features might be used in rather many places in main Sage and probably even more in personal code.
comment:22 Changed 3 years ago by
 Status changed from needs_review to needs_work
Back to "needs work" because it fails on nonint index sets.
comment:23 Changed 3 years ago by
 Commit changed from 188c6b11aa732cb8b368ad2574142e4ec79bd566 to 9afdabbab5ea056caf6309bfe63a80bcd4d4e933
Branch pushed to git repo; I updated commit sha1. New commits:
9afdabb  made reduced words available for nonstandard index sets

comment:24 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:25 followup: ↓ 28 Changed 3 years ago by
IMO, tuples and lists are the same thing except for hashability. So I don't think such a change is important.
That being said, braid_relations
should not be cached for the mutability (and it is not expensive enough or called often enough to warrant it).
comment:26 followup: ↓ 27 Changed 3 years ago by
or called often enough
The reason I added the cached_method
was the situation that I want to compute all reduced words of all elements in a group. I find it unreasonable to to explicitly compute the braid relations for each element again (which might take much more time than computing the orbit).
Just checked, it is an overhead of 10%.
comment:27 in reply to: ↑ 26 Changed 3 years ago by
 Status changed from needs_review to needs_work
Replying to stumpc5:
or called often enough
The reason I added the
cached_method
was the situation that I want to compute all reduced words of all elements in a group. I find it unreasonable to to explicitly compute the braid relations for each element again (which might take much more time than computing the orbit).Just checked, it is an overhead of 10%.
It is mutable output, therefore should not be a cached_method
.
I am also being wary of an overreliance on caching things, which can lead to memory leaks (nearly everything for this implementation is cached, which I am not saying it does give a memory leak, but it does bloat the memory usage.)
comment:28 in reply to: ↑ 25 Changed 3 years ago by
Replying to tscrim:
IMO, tuples and lists are the same thing except for hashability. So I don't think such a change is important.
Its not important, but why mess up people's code with random unnecessary changes? The reduced_words
code has been in Sage for a long time and the choice was made that it would return lists. For instance (and I'm not a big user of reduced words), but I looked in some of my files and found random places where code would need to be updated e.g.:
def gen_loops( w ): R = w.reduced_words() if w==G.first(): return [(0,0),(1,1),(2,2),(3,3)] return map(tuple,[w1 + list(reversed(w2)) for w1 in R for w2 in R if w1[1]!=w2[1]])
Simple fix... but I would request that you don't make a change like that unless its necessary.
comment:29 Changed 3 years ago by
 Commit changed from 9afdabbab5ea056caf6309bfe63a80bcd4d4e933 to 97170f3f2b0e7a5766a6314035963c801ff2ef5b
Branch pushed to git repo; I updated commit sha1. New commits:
97170f3  moved tuples to lists in reduced words as requested by Mike

comment:30 Changed 3 years ago by
 Commit changed from 97170f3f2b0e7a5766a6314035963c801ff2ef5b to 8278b0c8d02622f188de38fcae8d2a7754dad011
Branch pushed to git repo; I updated commit sha1. New commits:
8278b0c  moved code to function 'braid_orbit' and added more documentation

comment:31 Changed 3 years ago by
 Commit changed from 8278b0c8d02622f188de38fcae8d2a7754dad011 to 1303b217c33a1d831a691e25ec0b3d6a8a5f3294
Branch pushed to git repo; I updated commit sha1. New commits:
1303b21  removed cached method from braid relations

comment:32 Changed 3 years ago by
Hi Travis, I agree that values of cached methods should be immutable. On the other hand, I do not agree that such rather cheap methods should not be cached. I'd rather think that all sort of "elementary information" about Coxeter groups should be cached. This is because there are simply not many Coxeter groups, so saving such information will never fill up the memory (unless you want to keep zillions of Coxeter groups in memory together with tons of their elementary information). It is a totally different situation for element methods where it is much more crucial to keep track of which information should be kept in memory and which should rather be recomputed per default.
This being said, I don't care enough here, so I simply removed the chached_method
.
comment:33 Changed 3 years ago by
 Status changed from needs_work to needs_review
comment:34 Changed 3 years ago by
 Status changed from needs_review to positive_review
Like I said, I am just expressing my caution on caching everything; I did not mean to imply that it had to be removed for a positive review (except for the mutability issue).
Thank you for all the fixes.
comment:35 Changed 3 years ago by
 Status changed from positive_review to needs_work
sage t long src/sage/categories/coxeter_groups.py # 4 doctests failed
comment:36 Changed 3 years ago by
 Commit changed from 1303b217c33a1d831a691e25ec0b3d6a8a5f3294 to b4ebf17b588dbc1e7fedd038e3ca526fcb6a2785
comment:37 Changed 3 years ago by
 Status changed from needs_work to positive_review
Some tests needed to be marked as gap3
.
comment:38 Changed 3 years ago by
 Branch changed from public/combinat/reduced_words_coxeter_groups25485 to b4ebf17b588dbc1e7fedd038e3ca526fcb6a2785
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
added cython implementation