#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: |
Status badges
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 12 years ago by
comment:1 Changed 12 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 6 Changed 12 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 12 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 12 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 12 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 12 years ago by
- Description modified (diff)
comment:8 in reply to: ↑ 6 Changed 12 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 12 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.