#13406: Optimize CombinatorialFreeModule.Element._vector_
-------------------------------------+--------------------------------------
Reporter: nthiery | Owner: jason, was
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-5.4
Component: linear algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers: Mathieu Guay-Paquet,
Franco Saliola,
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: | Stopgaps:
-------------------------------------+--------------------------------------
Changes (by mguaypaq):
* status: needs_review => positive_review
Old description:
> Converting a {{{CombinatorialFreeModule}}} element to a vector (i.e.
> dense
> {{{FreeModule}}} element) was ridiculously slow:
>
> Before:
> {{{
> sage: sage: F = CombinatorialFreeModule(QQ, range(10))
> sage: f = F.an_element()
> sage: %timeit f._vector_()
> 625 loops, best of 3: 142 µs per loop
> sage: %timeit f.to_vector()
> 625 loops, best of 3: 143 µs per loop
> sage: %timeit vector(f)
> 625 loops, best of 3: 159 µs per loop
> }}}
>
> After:
> {{{
> sage: F = CombinatorialFreeModule(QQ, range(10))
> sage: f = F.an_element()
> sage: %timeit f._vector_()
> 625 loops, best of 3: 17.7 µs per loop
> sage: %timeit f.to_vector()
> 625 loops, best of 3: 17.5 µs per loop
> sage: %timeit vector(f)
> 625 loops, best of 3: 34.6 µs per loop
> }}}
>
> This impacts for example Weyl group actions, and thus lots of the root
> systems arithmetic.
>
> Before:
> {{{
> sage: W = WeylGroup(["A",5])
> sage: %time l = list(W)
> CPU times: user 3.55 s, sys: 0.00 s, total: 3.55 s
> Wall time: 3.57 s
> }}}
>
> After:
> {{{
> sage: W = WeylGroup(["A",5])
> sage: %time l = list(W)
> CPU times: user 2.80 s, sys: 0.00 s, total: 2.81 s
> Wall time: 2.81 s
> }}}
New description:
Converting a {{{CombinatorialFreeModule}}} element to a vector (i.e. dense
{{{FreeModule}}} element) was ridiculously slow:
Before:
{{{
sage: F = CombinatorialFreeModule(QQ, range(10))
sage: f = F.an_element()
sage: %timeit f._vector_()
625 loops, best of 3: 142 µs per loop
sage: %timeit f.to_vector()
625 loops, best of 3: 143 µs per loop
sage: %timeit vector(f)
625 loops, best of 3: 159 µs per loop
}}}
After:
{{{
sage: F = CombinatorialFreeModule(QQ, range(10))
sage: f = F.an_element()
sage: %timeit f._vector_()
625 loops, best of 3: 17.7 µs per loop
sage: %timeit f.to_vector()
625 loops, best of 3: 17.5 µs per loop
sage: %timeit vector(f)
625 loops, best of 3: 34.6 µs per loop
}}}
This impacts for example Weyl group actions, and thus lots of the root
systems arithmetic.
Before:
{{{
sage: W = WeylGroup(["A",5])
sage: %time l = list(W)
CPU times: user 3.55 s, sys: 0.00 s, total: 3.55 s
Wall time: 3.57 s
}}}
After:
{{{
sage: W = WeylGroup(["A",5])
sage: %time l = list(W)
CPU times: user 2.80 s, sys: 0.00 s, total: 2.81 s
Wall time: 2.81 s
}}}
--
Comment:
With the current patch, the code change makes sense, is well documented,
and I can reproduce the impressive speedups described in the ticked
description on my own machine. Also, the patchbot reports that all tests
pass on Sage 5.4.rc1 and that the documentation builds cleanly.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13406#comment:12>
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.
