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: sage-8.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:

Status badges

Description (last modified by stumpc5)

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 stumpc5

  • Branch set to u/stumpc5/reduced_words_in_coxeter_groups

comment:2 Changed 3 years ago by git

  • Commit set to 4736a75c29adac4349f7c4c63375367e84f2155e

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

4736a75added cython implementation

comment:3 Changed 3 years ago by stumpc5

  • Authors set to Christian Stump
  • 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 git

  • Commit changed from 4736a75c29adac4349f7c4c63375367e84f2155e to e8ed32b4a2e570f44fa8abaf8286262f9e5d8e07

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

e8ed32badded documentation

comment:5 Changed 3 years ago by git

  • Commit changed from e8ed32b4a2e570f44fa8abaf8286262f9e5d8e07 to 7c55fab75053432140611e4f10a8c06abad8f05b

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

7c55fabremoved commented old method

comment:6 Changed 3 years ago by stumpc5

okay, now ready for review

comment:7 Changed 3 years ago by git

  • Commit changed from 7c55fab75053432140611e4f10a8c06abad8f05b to 310c0bee592bb64622914e8030474864ead18329

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

c954af8Adding some documentation.
310c0beMerge branch 't/25487/bug_in_the_minimal__non__working_example_of_a_finite_coxeter_group' into t/25485/reduced_words_in_coxeter_groups

comment:8 Changed 3 years ago by 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

comment:9 Changed 3 years ago by tscrim

  • Branch changed from u/stumpc5/reduced_words_in_coxeter_groups to public/combinat/reduced_words_coxeter_groups-25485
  • Commit changed from 310c0bee592bb64622914e8030474864ead18329 to 5b670a59b4ad75a23b6a2b8bec659e0c1d71cd3e
  • Reviewers set to Travis Scrimshaw

New commits:

efe0b33Getting some more speed out and other small fixes.
5b670a5Making _braid_relations public again.

comment:10 Changed 3 years ago by git

  • Commit changed from 5b670a59b4ad75a23b6a2b8bec659e0c1d71cd3e to 4de48f57af5980b4af33ca6a5e6302aa77d50b40

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

99740b3fixed a bug in reflection group that labels are not propagated to cartan type
936b581let the braid relations for real reflection groups use the generic code
4de48f5added the braid group now as it is there

comment:11 Changed 3 years ago by stumpc5

  • Status changed from needs_review to positive_review

comment:12 Changed 3 years ago by tscrim

  • Status changed from positive_review to needs_work

Failing doctests. Currently fixing.

comment:13 Changed 3 years ago by git

  • Commit changed from 4de48f57af5980b4af33ca6a5e6302aa77d50b40 to 188c6b11aa732cb8b368ad2574142e4ec79bd566

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

188c6b1Fixing doctest failures.

comment:14 follow-up: Changed 3 years ago by tscrim

  • 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 k-Schur function book tests.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 3 years ago by 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.

comment:16 in reply to: ↑ 15 Changed 3 years ago by 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.)

comment:17 Changed 3 years ago by 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.

comment:18 Changed 3 years ago by 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.

comment:19 Changed 3 years ago by 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())]

?

comment:20 Changed 3 years ago by 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

comment:21 Changed 3 years ago by 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.

Last edited 3 years ago by stumpc5 (previous) (diff)

comment:22 Changed 3 years ago by stumpc5

  • Status changed from needs_review to needs_work

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

comment:23 Changed 3 years ago by git

  • Commit changed from 188c6b11aa732cb8b368ad2574142e4ec79bd566 to 9afdabbab5ea056caf6309bfe63a80bcd4d4e933

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

9afdabbmade reduced words available for non-standard index sets

comment:24 Changed 3 years ago by stumpc5

  • Status changed from needs_work to needs_review

comment:25 follow-up: Changed 3 years ago by 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).

comment:26 follow-up: Changed 3 years ago by 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%.

comment:27 in reply to: ↑ 26 Changed 3 years ago by tscrim

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

comment:28 in reply to: ↑ 25 Changed 3 years ago by 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.

comment:29 Changed 3 years ago by git

  • Commit changed from 9afdabbab5ea056caf6309bfe63a80bcd4d4e933 to 97170f3f2b0e7a5766a6314035963c801ff2ef5b

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

97170f3moved tuples to lists in reduced words as requested by Mike

comment:30 Changed 3 years ago by git

  • Commit changed from 97170f3f2b0e7a5766a6314035963c801ff2ef5b to 8278b0c8d02622f188de38fcae8d2a7754dad011

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

8278b0cmoved code to function 'braid_orbit' and added more documentation

comment:31 Changed 3 years ago by git

  • Commit changed from 8278b0c8d02622f188de38fcae8d2a7754dad011 to 1303b217c33a1d831a691e25ec0b3d6a8a5f3294

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

1303b21removed cached method from braid relations

comment:32 Changed 3 years ago by 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.

comment:33 Changed 3 years ago by stumpc5

  • Status changed from needs_work to needs_review

comment:34 Changed 3 years ago by tscrim

  • 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 vbraun

  • 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 git

  • Commit changed from 1303b217c33a1d831a691e25ec0b3d6a8a5f3294 to b4ebf17b588dbc1e7fedd038e3ca526fcb6a2785

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

8a03402Merge branch 'public/combinat/reduced_words_coxeter_groups-25485' of git://trac.sagemath.org/sage into public/combinat/reduced_words_coxeter_groups-25485
b4ebf17Marking some more tests as gap3.

comment:37 Changed 3 years ago by tscrim

  • Status changed from needs_work to positive_review

Some tests needed to be marked as gap3.

comment:38 Changed 3 years ago by vbraun

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