Ticket #7754 (closed enhancement: fixed)

Opened 8 months ago

Last modified 8 months ago

Weyl group optimizations

Reported by: nthiery Owned by: nthiery
Priority: major Milestone: sage-4.3.1
Component: combinatorics Keywords: Weyl groups
Cc: bump Author(s): Nicolas M. Thiéry
Report Upstream: N/A Reviewer(s): Daniel Bump
Merged in: sage-4.3.1.alpha0 Work issues:

Description (last modified by nthiery) (diff)

  • 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

trac_7754_weyl_group_optimizations-nt.patch Download (2.2 KB) - added by nthiery 8 months ago.

Change History

Changed 8 months ago by nthiery

  Changed 8 months ago by nthiery

  • status changed from new to needs_review
  • description modified (diff)

follow-up: ↓ 6   Changed 8 months ago by bump

  • status changed from needs_review to positive_review
  • summary changed from Weyl group optimizations to Weyl 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.

  Changed 8 months ago by nthiery

  • milestone set to sage-4.3.1

Thanks Dan for the review!

  Changed 8 months ago by mhansen

  • status changed from positive_review to closed
  • resolution set to fixed
  • merged set to sage-4.3.1.alpha0

  Changed 8 months ago by mvngu

  • summary changed from Weyl group optimizations [with patch, positive review] to Weyl group optimizations

in reply to: ↑ 2 ; follow-up: ↓ 8   Changed 8 months ago by mvngu

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?

  Changed 8 months ago by nthiery

  • description modified (diff)

in reply to: ↑ 6   Changed 8 months ago by nthiery

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!

  Changed 8 months ago by nthiery

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