#13406: Optimize CombinatorialFreeModule.Element._vector_
-------------------------------------+--------------------------------------
Reporter: nthiery | Owner: jason, was
Type: enhancement | Status: needs_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 nthiery):
* status: needs_work => needs_review
* reviewer: => Mathieu Guay-Paquet, Franco Saliola,
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: 18.4 µs per loop
> sage: %timeit f.to_vector()
> 625 loops, best of 3: 18.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: 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:
Done! I could not find back the code, so I rewrote it (and gained another
micro second :-))
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13406#comment:11>
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.
