#7754: Weyl group optimizations
-------------------------------+--------------------------------------------
Reporter: nthiery | Owner: nthiery
Type: enhancement | Status: closed
Priority: major | Milestone: sage-4.3.1
Component: combinatorics | Resolution: fixed
Keywords: Weyl groups | Work_issues:
Author: Nicolas M. Thiéry | Upstream: N/A
Reviewer: Daniel Bump | Merged: sage-4.3.1.alpha0
-------------------------------+--------------------------------------------
Description changed by nthiery:
Old description:
> - 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.40 s, sys: 0.00 s, total: 1.41 s Wall time: 1.42 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.71 s, sys: 0.01 s, total: 1.72 s Wall time: 1.72 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, ...).
New description:
- 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, ...).
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7754#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
