#13406: Optimize CombinatorialFreeModule.Element._vector_
-------------------------------------+--------------------------------------
Reporter: nthiery | Owner: jason, was
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.4
Component: linear algebra | Resolution:
Keywords: | Work issues:
Report Upstream: N/A | Reviewers:
Authors: Nicolas M. Thiéry | Merged in:
Dependencies: | Stopgaps:
-------------------------------------+--------------------------------------
Changes (by mguaypaq):
* cc: mguaypaq (added)
* status: needs_review => needs_work
Old description:
> Converting a CombinatorialFreeModule element to a vector (e.g. 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: 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
}}}
--
Comment:
As far as I can tell, the patch as posted does not functionally change
anything. It changes the documentation of
{{{CombinatorialFreeModuleElement._vector_}}} without changing the
corresponding code, and adds the method
{{{CombinatorialFreeModule._dense_free_module}}} without adding any code
to have it called.
I confirmed this experimentally by getting the following timings on
sage-5.3 for the first three tests in the ticket description
({{{f._vector_()}}}, {{{f.to_vector()}}}, {{{vector(f)}}}):
Before: 270, 270, 293 µs
[[BR]]
After: 265, 266, 290 µs
and also by adding a {{{print}}} statement to {{{_dense_free_module}}} (so
that I know the code is never called). I got similar results by trying
this on sage-5.3 + combinat.
Is it possible that the patch file got corrupted, or that it is based on
an already modified version of Sage, or that there is an unstated
dependency which introduces {{{_dense_free_module}}} as a hook?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13406#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.
