#15760: Speed up short vector enumeration
-------------------------------------+-------------------------------------
Reporter: jdemeyer | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.1
Component: performance | Resolution:
Keywords: | Merged in:
Authors: Jeroen Demeyer | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jdemeyer/ticket/15760 | 8c1245926c73f1692dbdd2d3da07dacb7b6e50b5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by jdemeyer):
* commit: => 8c1245926c73f1692dbdd2d3da07dacb7b6e50b5
Old description:
> The `short_vector_list_up_to_length` method of quadratic forms uses GP
> but the interface is so badly done that the majority of the time is taken
> up by the Sage interface, and not by the actual computation. Still, even
> with the new implementation, most time is taken by the conversion to
> vectors.
>
> Timings before:
> {{{
> sage: qf = QuadraticForm(matrix(3, [2, 1, 1, 1, 2, 1, 1, 1, 2]))
> sage: %timeit qf.short_vector_list_up_to_length(100)
> 1 loops, best of 3: 1.13 s per loop
> sage: %timeit qf.short_vector_list_up_to_length(1000)
> 1 loops, best of 3: 6.74 s per loop
> }}}
>
> Timings after:
> {{{
> sage: qf = QuadraticForm(matrix(3, [2, 1, 1, 1, 2, 1, 1, 1, 2]))
> sage: %timeit qf.short_vector_list_up_to_length(100)
> 10 loops, best of 3: 34.4 ms per loop
> sage: %timeit qf.short_vector_list_up_to_length(1000)
> 1 loops, best of 3: 1.03 s per loop
> }}}
New description:
The `short_vector_list_up_to_length` method of quadratic forms uses GP but
the interface is so badly done that the majority of the time is taken up
by the Sage interface, and not by the actual computation. Still, even with
the new implementation, most time is taken by the conversion from PARI to
Sage vectors.
Timings before:
{{{
sage: qf = QuadraticForm(matrix(3, [2, 1, 1, 1, 2, 1, 1, 1, 2]))
sage: %timeit qf.short_vector_list_up_to_length(100)
1 loops, best of 3: 1.13 s per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 6.74 s per loop
}}}
Timings after:
{{{
sage: qf = QuadraticForm(matrix(3, [2, 1, 1, 1, 2, 1, 1, 1, 2]))
sage: %timeit qf.short_vector_list_up_to_length(100)
10 loops, best of 3: 34.4 ms per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 1.03 s per loop
}}}
--
Comment:
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=8c1245926c73f1692dbdd2d3da07dacb7b6e50b5
8c12459]||{{{Speed up short_vector_list_up_to_length()}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/15760#comment:3>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
