#7754 closed enhancement (fixed)
Weyl group optimizations
| Reported by: | Nicolas M. Thiéry | Owned by: | Nicolas M. Thiéry |
|---|---|---|---|
| Priority: | major | Milestone: | sage-4.3.1 |
| Component: | combinatorics | Keywords: | Weyl groups |
| Cc: | Daniel 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 13 years ago by
| Attachment: | trac_7754_weyl_group_optimizations-nt.patch added |
|---|
comment:1 Changed 13 years ago by
| Description: | modified (diff) |
|---|---|
| Status: | new → needs_review |
comment:2 follow-up: 6 Changed 13 years ago by
| Status: | needs_review → positive_review |
|---|---|
| Summary: | Weyl group optimizations → Weyl group optimizations [with patch, positive review] |
comment:4 Changed 13 years ago by
| Merged in: | → sage-4.3.1.alpha0 |
|---|---|
| Resolution: | → fixed |
| Status: | positive_review → closed |
comment:5 Changed 13 years ago by
| Summary: | Weyl group optimizations [with patch, positive review] → Weyl group optimizations |
|---|
comment:6 follow-up: 8 Changed 13 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 13 years ago by
| Description: | modified (diff) |
|---|
comment:8 Changed 13 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 13 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.