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

Status badges

Description (last modified by stumpc5)

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 stumpc5

I will provide code in a minute; any suggestions how to properly do get the number of reflections in the fastest way for WeylGroups or CoxeterGroups? Currently, it uses the definition of the degrees, but that is too slow given that it should and can be fast.

comment:2 Changed 5 years ago by stumpc5

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 stumpc5

  • Branch set to u/stumpc5/20943

comment:4 Changed 5 years ago by stumpc5

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 stumpc5

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

  • Status changed from new to needs_review

comment:7 Changed 5 years ago by chapoton

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

dad4de4fixed the bux
aaf771eMerge branch 'develop' into u/stumpc5/20943

comment:8 Changed 5 years ago by chapoton

the doctests are missing the # optional

comment:9 Changed 5 years ago by stumpc5

Okay, I guess you are right. I should and will do it properly:

  1. make the method ReflectionGroup.number_of_reflections use the attribute ReflectionGroup._number_of_reflections instead of recomputing it,
  1. make this flip code use the method instead of the attribute for ReflectionGroup and also use this attribute for WeylGroup and CoxeterGroup, and finally
  1. make WeylGroup and CoxeterGroup compute the number of reflections in the fastest possible way.

comment:10 Changed 5 years ago by git

  • Commit changed from aaf771ed669652a1b09d69b5e7c539afa950120a to f17422a1df8f9a0d15f7d51f7340f416625c4417

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

f17422aworking out the proper way to compute the number of reflections

comment:11 Changed 5 years ago by git

  • Commit changed from f17422a1df8f9a0d15f7d51f7340f416625c4417 to 6e97757e2d1181e51ea381a49161e157b6df5418

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

6e97757updated the new doctests to be optional

comment:12 Changed 5 years ago by chapoton

ok. Looks much better.

Have you re-done 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 git

  • Commit changed from 6e97757e2d1181e51ea381a49161e157b6df5418 to 35a98d714455b0c2408e0420550997c0f7232dd9

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

35a98d7fixed the new doctests, all tests seem to pass now

comment:14 Changed 5 years ago by stumpc5

The timings should still be the old as the change

-            return ZZ.sum(self.degrees()) - self.rank()
+            return ZZ.sum(deg-1 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 follow-up: Changed 5 years ago by stumpc5

But I think that should go into a different ticket.

comment:16 in reply to: ↑ 15 Changed 5 years ago by chapoton

Replying to stumpc5:

But I think that should go into a different ticket.

ok, indeed.

comment:17 follow-up: Changed 5 years ago by chapoton

An idea: why not make number_of_reflection a cached_method in all cases?

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

comment:18 Changed 5 years ago by stumpc5

That is now #20956.

comment:19 in reply to: ↑ 17 Changed 5 years ago by stumpc5

Replying to chapoton:

An idea: why not make number_of_reflection a cached_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 stumpc5

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 git

  • Commit changed from 35a98d714455b0c2408e0420550997c0f7232dd9 to 250aaee516c3ee3cee3751090e5435d94b79b998

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

250aaeeadded cached methods to number of reflections/hyperplanes and rank

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

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 stumpc5

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?

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

comment:24 Changed 5 years ago by chapoton

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 git

  • Commit changed from 250aaee516c3ee3cee3751090e5435d94b79b998 to 6f2172b794ec53d55bd7920125b92662dc17edc8

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

6f2172breplaced _number_of_reflections by number_of_reflections() everywhere

comment:26 follow-up: Changed 5 years ago by chapoton

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

Replying to chapoton:

ok, let it be.

thanks!

comment:28 Changed 5 years ago by tscrim

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 vbraun

  • Branch changed from u/stumpc5/20943 to 6f2172b794ec53d55bd7920125b92662dc17edc8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.