#7754 closed enhancement (fixed)
Weyl group optimizations
| Reported by: | nthiery | Owned by: | nthiery |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.3.1 |
| Component: | combinatorics | Keywords: | Weyl groups |
| Cc: | bump | Merged in: | sage-4.3.1.alpha0 |
| Authors: | Nicolas M. Thiéry | Reviewers: | Daniel Bump |
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Description (last modified by )
- faster hash method calling the hash of the underlying matrix (which is set as immutable for that purpose)
- new eq method
- action on the weight lattice realization: optimization of the matrix multiplication
Depends (trivially) on #7753
This indirectly improve most Weyl group routines:
Without the patch:
sage: W = WeylGroup(["F",4]) sage: W.cardinality() 1152 sage: time l=list(W) CPU times: user 12.14 s, sys: 0.06 s, total: 12.20 s Wall time: 12.20 s sage: W = WeylGroup(["E",8]) sage: time w0 = W.long_element() CPU times: user 1.71 s, sys: 0.01 s, total: 1.72 s Wall time: 1.72 s
With the patch:
sage: W = WeylGroup(["F",4]) sage: W.cardinality() 1152 sage: time l=list(W) CPU times: user 7.96 s, sys: 0.04 s, total: 8.00 s Wall time: 8.01 s sage: W = WeylGroup(["E",8]) sage: time w0 = W.long_element() CPU times: user 1.40 s, sys: 0.00 s, total: 1.41 s Wall time: 1.42 s
Honestly, this is still ridiculously slow; luckily there still is much room left for improvements by improved caching and optimizations of the underlying tools (CombinatorialFreeModules?, ...).
Attachments (1)
Change History (10)
Changed 7 years ago by
comment:1 Changed 7 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 6 Changed 7 years ago by
- Status changed from needs_review to positive_review
- Summary changed from Weyl group optimizations to Weyl group optimizations [with patch, positive review]
comment:4 Changed 7 years ago by
- Merged in set to sage-4.3.1.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:5 Changed 7 years ago by
- Summary changed from Weyl group optimizations [with patch, positive review] to Weyl group optimizations
comment:6 in reply to: ↑ 2 ; follow-up: ↓ 8 Changed 7 years ago by
Replying to bump:
It is a very substantial speed-up. It cuts a few seconds off
sage -t weyl_groups.pybut more importantly it about doubles the speed of computing the reduced word of a Weyl group element, which is the basis of most combinatorial algorithms.
Hi Dan and Nicolas,
I'm doing a release tour of the features of this ticket, see the Sage wiki page. Is there some sample code I could use to show the speed-up implemented by this ticket?
comment:7 Changed 7 years ago by
- Description modified (diff)
comment:8 in reply to: ↑ 6 Changed 7 years ago by
Hi Dan and Nicolas,
I'm doing a release tour of the features of this ticket, see the Sage wiki page. Is there some sample code I could use to show the speed-up implemented by this ticket?
Yup, see the updated description!
comment:9 Changed 7 years ago by
- Description modified (diff)
I tested this patch without #7753. I tested it with and without the patch in #7751.
It is a very substantial speedup. It cuts a few seconds off
sage -t weyl_groups.pybut more importantly it about doubles the speed of computing the reduced word of a Weyl group element, which is the basis of most combinatorial algorithms.There are three patch fragments, one replacing the hash method with the hash of the underlying matrix, one replacing the
__eq__method, and one unraveling some unnecessary complexity in the Weyl group action. I tested each patch fragment separately and found that they are all speedups, the last one being very significant.