Opened 5 years ago
Closed 5 years ago
#20943 closed enhancement (fixed)
Update a missing important speed improvement for subword complexes
Reported by:  stumpc5  Owned by:  

Priority:  major  Milestone:  sage7.3 
Component:  combinatorics  Keywords:  reflection group, coxeter group, subword complex, days80 
Cc:  tscrim, chapoton, nthiery  Merged in:  
Authors:  Christian Stump  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  6f2172b (Commits, GitHub, GitLab)  Commit:  6f2172b794ec53d55bd7920125b92662dc17edc8 
Dependencies:  Stopgaps: 
Description (last modified by )
The method _flip_c
currently uses
nr_ref = len(W.long_element(as_word=True))
which drastically slows down computations (here: the construction of cluster complexes using subword complexes through the greedy flip algorithm).
Change History (29)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
For Weyl groups, I get
sage: W = WeylGroup(['E',7]) sage: %timeit len(W.long_element(as_word=True)) 10 loops, best of 3: 98.6 ms per loop sage: %timeit W.number_of_reflections() 1 loop, best of 3: 208 ms per loop
and for Coxeter groups, I get
sage: W = CoxeterGroup(['E',7]) sage: %timeit len(W.long_element(as_word=True)) 1 loop, best of 3: 206 ms per loop sage: %timeit W.number_of_reflections() 1 loop, best of 3: 378 ms per loop
so I leave the current implementation for those (though this is not as clean as it should be).
comment:3 Changed 5 years ago by
 Branch set to u/stumpc5/20943
comment:4 Changed 5 years ago by
sage: W = ReflectionGroup(['A',6]); c = list(W.index_set()) sage: Q = c+W.w0.coxeter_sorting_word(c) sage: %time S = SubwordComplex(Q,W.w0,algorithm="greedy")
with the fix, I get
CPU times: user 222 ms, sys: 16.1 ms, total: 238 ms Wall time: 248 ms
and without the fix, I get
CPU times: user 1.35 s, sys: 37.7 ms, total: 1.39 s Wall time: 1.4 s
For types E, it becomes obviously much worse.
comment:5 Changed 5 years ago by
 Description modified (diff)
I tried to push and to set the branch by hand, but I am not sure it actually worked...
comment:6 Changed 5 years ago by
 Status changed from new to needs_review
comment:7 Changed 5 years ago by
 Commit set to aaf771ed669652a1b09d69b5e7c539afa950120a
Sorry, but I do not understand the logic of your change.
What is this attribute __number_of_reflections
? Does it exist only in the complex reflection group implementation ?
One should also replace the default code for number_of_reflections
by the faster
from sage.rings.all import ZZ return ZZ.sum(self.degrees()  1)
that avoid to use rank.
New commits:
dad4de4  fixed the bux

aaf771e  Merge branch 'develop' into u/stumpc5/20943

comment:8 Changed 5 years ago by
the doctests are missing the # optional
comment:9 Changed 5 years ago by
Okay, I guess you are right. I should and will do it properly:
 make the method
ReflectionGroup.number_of_reflections
use the attributeReflectionGroup._number_of_reflections
instead of recomputing it,
 make this flip code use the method instead of the attribute for
ReflectionGroup
and also use this attribute forWeylGroup
andCoxeterGroup
, and finally
 make
WeylGroup
andCoxeterGroup
compute the number of reflections in the fastest possible way.
comment:10 Changed 5 years ago by
 Commit changed from aaf771ed669652a1b09d69b5e7c539afa950120a to f17422a1df8f9a0d15f7d51f7340f416625c4417
Branch pushed to git repo; I updated commit sha1. New commits:
f17422a  working out the proper way to compute the number of reflections

comment:11 Changed 5 years ago by
 Commit changed from f17422a1df8f9a0d15f7d51f7340f416625c4417 to 6e97757e2d1181e51ea381a49161e157b6df5418
Branch pushed to git repo; I updated commit sha1. New commits:
6e97757  updated the new doctests to be optional

comment:12 Changed 5 years ago by
ok. Looks much better.
Have you redone the timings to compare the new "number_of_reflections" with the previously used len of the longest word ?
comment:13 Changed 5 years ago by
 Commit changed from 6e97757e2d1181e51ea381a49161e157b6df5418 to 35a98d714455b0c2408e0420550997c0f7232dd9
Branch pushed to git repo; I updated commit sha1. New commits:
35a98d7  fixed the new doctests, all tests seem to pass now

comment:14 Changed 5 years ago by
The timings should still be the old as the change
 return ZZ.sum(self.degrees())  self.rank() + return ZZ.sum(deg1 for deg in self.degrees())
should not make any difference... (just checked, no change there). It would be better if we either do a speed improvement of the degrees
method for WeylGroup
and CoxeterGroup
, or make number_of_reflections
there use the length of the longest element there instead.
comment:15 followup: ↓ 16 Changed 5 years ago by
But I think that should go into a different ticket.
comment:16 in reply to: ↑ 15 Changed 5 years ago by
comment:17 followup: ↓ 19 Changed 5 years ago by
An idea: why not make number_of_reflection
a cached_method
in all cases?
comment:18 Changed 5 years ago by
That is now #20956.
comment:19 in reply to: ↑ 17 Changed 5 years ago by
Replying to chapoton:
An idea: why not make
number_of_reflection
acached_method
in all cases?
Why not, we could also do that. Maybe that's even the "right" solution, as the caching doesn't take any memory while avoids recomputing a bigger computation again and again.
comment:20 Changed 5 years ago by
If you do not object, I would add this here to this ticket and make the other a duplicate.
comment:21 Changed 5 years ago by
 Commit changed from 35a98d714455b0c2408e0420550997c0f7232dd9 to 250aaee516c3ee3cee3751090e5435d94b79b998
Branch pushed to git repo; I updated commit sha1. New commits:
250aaee  added cached methods to number of reflections/hyperplanes and rank

comment:22 followup: ↓ 23 Changed 5 years ago by
ok, then you can get rid of the attribute and the method in reflection_group_complex
comment:23 in reply to: ↑ 22 Changed 5 years ago by
Replying to chapoton:
ok, then you can get rid of the attribute and the method in reflection_group_complex
Out of curiosity: is it faster to use a cached method, or to use an attribute? Or is that difference never important?
comment:24 Changed 5 years ago by
I do not know, sorry. I guess both are fast enough for our purposes, but we can aim for simplicity for the moment, maybe ?
comment:25 Changed 5 years ago by
 Commit changed from 250aaee516c3ee3cee3751090e5435d94b79b998 to 6f2172b794ec53d55bd7920125b92662dc17edc8
Branch pushed to git repo; I updated commit sha1. New commits:
6f2172b  replaced _number_of_reflections by number_of_reflections() everywhere

comment:26 followup: ↓ 27 Changed 5 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be.
comment:27 in reply to: ↑ 26 Changed 5 years ago by
comment:28 Changed 5 years ago by
Just FYI  calling a @cached_method
is ~10% slower than a (Python) attribute lookup:
sage: class Foo(object): ....: def __init__(self, x): ....: self.x = x ....: self._y = x ....: @cached_method ....: def y(self): ....: return self._y ....: sage: F = Foo(5) sage: %timeit F.x The slowest run took 73.41 times longer than the fastest. This could mean that an intermediate result is being cached. 10000000 loops, best of 3: 42.2 ns per loop sage: %timeit F.y() The slowest run took 2799.35 times longer than the fastest. This could mean that an intermediate result is being cached. 10000000 loops, best of 3: 57.1 ns per loop
However, it is better code (IMO) to use the cached method mechanism, and it makes it easier to change/override it.
comment:29 Changed 5 years ago by
 Branch changed from u/stumpc5/20943 to 6f2172b794ec53d55bd7920125b92662dc17edc8
 Resolution set to fixed
 Status changed from positive_review to closed
I will provide code in a minute; any suggestions how to properly do get the number of reflections in the fastest way for
WeylGroups
orCoxeterGroups
? Currently, it uses the definition of the degrees, but that is too slow given that it should and can be fast.