#15758: Reimplement short vector enumeration
-------------------------------+-------------------------------
Reporter: mraum | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.1
Component: quadratic forms | Keywords:
Merged in: | Authors: Martin Raum
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-------------------------------+-------------------------------
QuadraticForm(...).short_vector_list_up_to_length(...) currently uses
PARI, which provides an incorrect implementation (see #13531). Here is a
correct one, which is also faster. For comparison, here are the timings
before and 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)
1 loops, best of 3: 1.1 s per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 7.42 s per loop
}}}
{{{
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: 360 ms per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 11.5 s per loop
}}}
As a big bonus (at least to me), we have a version that doesn't come with
conversion to vectors:
{{{
sage: from
sage.quadratic_forms.enumerate_short_vectors.enumerate_short_vectors_python
import short_vectors
sage: %timeit short_vectors(qf.matrix(), 0, 1000)
10 loops, best of 3: 65.7 ms per loop
}}}
This depends on boost::python, which hopefully will be integrated soon.
Until then, note that you have to have boost_python library installed (we
have the headers already).
--
Ticket URL: <http://trac.sagemath.org/ticket/15758>
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.
