Opened 8 years ago
Last modified 7 years ago
#15758 new enhancement
Reimplement short vector enumeration
Reported by:  mraum  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  quadratic forms  Keywords:  
Cc:  akoutsianas  Merged in:  
Authors:  Martin Raum  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/mraum/ticket/15758 (Commits, GitHub, GitLab)  Commit:  5ba169fbf00d249938a083e30671c38b758b89d7 
Dependencies:  Stopgaps: 
Description
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).
Change History (11)
comment:1 Changed 8 years ago by
 Branch set to u/mraum/ticket/15758
 Created changed from 01/29/14 08:19:47 to 01/29/14 08:19:47
 Modified changed from 01/29/14 08:19:47 to 01/29/14 08:19:47
comment:2 Changed 8 years ago by
 Commit set to 5ba169fbf00d249938a083e30671c38b758b89d7
comment:3 Changed 8 years ago by
On my system, the following changes were needed to make this compile:

src/module_list.py
diff git a/src/module_list.py b/src/module_list.py index e3a6ea9..c567ee6 100755
a b ext_modules = [ 1475 1475 depends = ['sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors_boost_python.hpp', 1476 1476 'sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors.hpp'], 1477 1477 language = 'c++', 1478 extra_compile_args=[ 'std=c++11'],1478 extra_compile_args=["std=c++0x"], 1479 1479 include_dirs = [SAGE_INC, SAGE_INC + '/python2.7', 'sage/c_libs/include'], 1480 libraries = ['stdc++', 'boost_python ', 'mpfi', 'mpfr', 'gmp']),1480 libraries = ['stdc++', 'boost_python2.7', 'mpfi', 'mpfr', 'gmp']), 1481 1481 1482 1482 Extension('sage.quadratic_forms.quadratic_form__evaluate', 1483 1483 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).
comment:4 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 8 years ago by
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 ?
comment:6 Changed 8 years ago by
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.
comment:7 Changed 8 years ago by
See #15976 for an interface to fpLLL's shortest vector implementation.
comment:8 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:9 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:10 Changed 7 years ago by
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
comment:11 Changed 7 years ago by
 Cc akoutsianas added
I know it's not needs_review, but you cannot yet rely on C++11. With GCC 4.6.3:
Last 10 new commits:
Add enumeration of short vectors to sage.
Refactor enumeration of short vectors
Sketch wrapper for enumeration of short vectors
Add cython wrapper to enumeration of short vectors.
Complete python interface for enumeration of short vectors.
Remove cython wrapper for enumeration of short vectors.
Update header and add missing implementation of enumeration internals.
Add enumeration of short vectors to the modulue list.
Update python wrapper for enumeration of short vectors.
Use new short vectors implementation in QuadraticForm(...).short_vector_list_up_to_length(...).