Reimplement short vector enumeration

[sagetrac-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).

CC: @sagetrac-akoutsianas

Component: quadratic forms

Author: Martin Raum

Branch/Commit: u/mraum/ticket/15758 @ 5ba169f

Issue created by migration from https://trac.sagemath.org/ticket/15758

[sagetrac-mraum]

Branch: u/mraum/ticket/15758

[jdemeyer]

Commit: 5ba169f

[jdemeyer]

comment:2

I know it's not needs_review, but you cannot yet rely on C++11. With GCC 4.6.3:

cc1plus: error: unrecognized command line option ‘-std=c++11’

---

Last 10 new commits:

2843bf3	Add enumeration of short vectors to sage.
f337fae	Refactor enumeration of short vectors
a6d5ce8	Sketch wrapper for enumeration of short vectors
b7dbede	Add cython wrapper to enumeration of short vectors.
269cc4b	Complete python interface for enumeration of short vectors.
aef8cf1	Remove cython wrapper for enumeration of short vectors.
3d33d53	Update header and add missing implementation of enumeration internals.
46f4d25	Add enumeration of short vectors to the modulue list.
1557395	Update python wrapper for enumeration of short vectors.
338ad31	Use new short vectors implementation in QuadraticForm(...).short_vector_list_up_to_length(...).

[jdemeyer]

comment:3

On my system, the following changes were needed to make this compile:

diff --git a/src/module_list.py b/src/module_list.py
index e3a6ea9..c567ee6 100755
--- a/src/module_list.py
+++ b/src/module_list.py
@@ -1475,9 +1475,9 @@ ext_modules = [
               depends = ['sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors_boost_python.hpp',
                          'sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors.hpp'],
               language = 'c++',
-              extra_compile_args=['-std=c++11'],
+              extra_compile_args=["-std=c++0x"],
               include_dirs = [SAGE_INC, SAGE_INC + '/python2.7', 'sage/c_libs/include'],
-              libraries = ['stdc++', 'boost_python', 'mpfi', 'mpfr', 'gmp']),
+              libraries = ['stdc++', 'boost_python-2.7', 'mpfi', 'mpfr', 'gmp']),
 
     Extension('sage.quadratic_forms.quadratic_form__evaluate',
               sources = ['sage/quadratic_forms/quadratic_form__evaluate.pyx']),

I don't know if everybody will be happy that the compiler now needs to support -std=c++0x (personally, I don't mind, especially given that Sage's GCC does support it).

[sagetrac-tmonteil]

comment:5

According to the changelog of fpLLL, a "short lattice vector enumeration algorithm" appeared in version 3.0 of fpLLL, which is a standard spkg of Sage. Why not interfacing with this implementation ?

[sagetrac-mraum]

comment:6

Honestly, before I implemented this (quite some time ago), I didn't find the short vector implementation in fpLLL's documentation. And I still don't.

It's a pity for my code, but I'm definitely in favor of wrapping the missing parts of fpLLL instead of my code. Clearly, fpLLL is a much more advanced implementation than I could implement.

Does anybody know how to invoke enumeration? It seems that topenum.h contains a class for this, but I can't figure out, what kind of date Enumerator.subTree contains.

[malb]

comment:7

See #15976 for an interface to fpLLL's shortest vector implementation.

[JohnCremona]

comment:10

As far as I know, the fpLLL library only deals with sublattices of ZZ^n, while pari can deal with enumerating short vectors when the Gram matrix is real. This is very important for my applications! So I would very much like this ticket to be revived.

Meanwhile, here is a bug report with the QuadraticForm class in this context, since it does not pass the optional flag=2 to pari's qfminim function when the Gram matrix is real:

sage: A = random_matrix(RR,5)
sage: A = A*A.transpose()
sage: Q = QuadraticForm(A)
sage: Q.short_vector_list_up_to_length(2)
...
PariError: incorrect type in qfminim0