Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#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 Nicolas M. Thiéry)

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

trac_7754_weyl_group_optimizations-nt.patch (2.2 KB) - added by Nicolas M. Thiéry 13 years ago.

Download all attachments as: .zip

Change History (10)

Changed 13 years ago by Nicolas M. Thiéry

comment:1 Changed 13 years ago by Nicolas M. Thiéry

Description: modified (diff)
Status: newneeds_review

comment:2 Changed 13 years ago by Daniel Bump

Status: needs_reviewpositive_review
Summary: Weyl group optimizationsWeyl group optimizations [with patch, positive review]

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.py but 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.

comment:3 Changed 13 years ago by Nicolas M. Thiéry

Milestone: sage-4.3.1

Thanks Dan for the review!

comment:4 Changed 13 years ago by Mike Hansen

Merged in: sage-4.3.1.alpha0
Resolution: fixed
Status: positive_reviewclosed

comment:5 Changed 13 years ago by Minh Van Nguyen

Summary: Weyl group optimizations [with patch, positive review]Weyl group optimizations

comment:6 in reply to:  2 ; Changed 13 years ago by Minh Van Nguyen

Replying to bump:

It is a very substantial speed-up. It cuts a few seconds off sage -t weyl_groups.py but 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 Nicolas M. Thiéry

Description: modified (diff)

comment:8 in reply to:  6 Changed 13 years ago by Nicolas M. Thiéry

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 Nicolas M. Thiéry

Description: modified (diff)
Note: See TracTickets for help on using tickets.