id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
15758,Reimplement short vector enumeration,mraum,,"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).",enhancement,new,major,sage-6.4,quadratic forms,,,akoutsianas,,Martin Raum,,N/A,,u/mraum/ticket/15758,5ba169fbf00d249938a083e30671c38b758b89d7,,