reduced words in coxeter groups

[stumpc5]

Implement the braid orbit of a reduced word (and thus all reduced words) in a Coxeter group

[git]

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

​4736a75

added cython implementation

[stumpc5]

have to add some doctests still.

Q: leave the old implementation or not?

[git]

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

​e8ed32b

added documentation

[git]

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

​7c55fab

removed commented old method

[stumpc5]

okay, now ready for review

[git]

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

​c954af8	Adding some documentation.
​310c0be	Merge branch 't/25487/bug_in_the_minimal__non__working_example_of_a_finite_coxeter_group' into t/25485/reduced_words_in_coxeter_groups

[tscrim]

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

[tscrim]

New commits:

​efe0b33	Getting some more speed out and other small fixes.
​5b670a5	Making _braid_relations public again.

[git]

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

​99740b3	fixed a bug in reflection group that labels are not propagated to cartan type
​936b581	let the braid relations for real reflection groups use the generic code
​4de48f5	added the braid group now as it is there

[tscrim]

Failing doctests. Currently fixing.

[git]

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

​188c6b1

Fixing doctest failures.

[tscrim]

Mike, Anne, I put you in cc because I had to change one of the k-Schur function book tests.

[aschilling]

Replying to tscrim:

Mike, Anne, I put you in cc because I had to change one of the k-Schur function book tests.

It only changes the order of the output, right? I guess that is ok.

[tscrim]

Replying to aschilling:

Replying to tscrim:

Mike, Anne, I put you in cc because I had to change one of the k-Schur 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.)

[zabrocki]

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.

[stumpc5]

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.

[zabrocki]

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())]

?

[stumpc5]

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

[stumpc5]

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.

[stumpc5]

Back to "needs work" because it fails on non-int index sets.

[git]

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

​9afdabb

made reduced words available for non-standard index sets

[tscrim]

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

[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%.

[tscrim]

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

[zabrocki]

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.

[git]

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

​97170f3

moved tuples to lists in reduced words as requested by Mike

[git]

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

​8278b0c

moved code to function 'braid_orbit' and added more documentation

[git]

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

​1303b21

removed cached method from braid relations

[stumpc5]

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.

[tscrim]

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.

[vbraun]

sage -t --long src/sage/categories/coxeter_groups.py  # 4 doctests failed

[git]

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

​8a03402	Merge branch 'public/combinat/reduced_words_coxeter_groups-25485' of git://trac.sagemath.org/sage into public/combinat/reduced_words_coxeter_groups-25485
​b4ebf17	Marking some more tests as gap3.

[tscrim]

Some tests needed to be marked as gap3.