Opened 5 years ago

Last modified 4 years ago

#15758 new enhancement

Reimplement short vector enumeration

Reported by: mraum Owned by:
Priority: major Milestone: sage-6.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) 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 5 years ago by mraum

  • 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 5 years ago by jdemeyer

  • Commit set to 5ba169fbf00d249938a083e30671c38b758b89d7

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:

2843bf3Add enumeration of short vectors to sage.
f337faeRefactor enumeration of short vectors
a6d5ce8Sketch wrapper for enumeration of short vectors
b7dbedeAdd cython wrapper to enumeration of short vectors.
269cc4bComplete python interface for enumeration of short vectors.
aef8cf1Remove cython wrapper for enumeration of short vectors.
3d33d53Update header and add missing implementation of enumeration internals.
46f4d25Add enumeration of short vectors to the modulue list.
1557395Update python wrapper for enumeration of short vectors.
338ad31Use new short vectors implementation in QuadraticForm(...).short_vector_list_up_to_length(...).

comment:3 Changed 5 years ago by jdemeyer

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 = [ 
    14751475              depends = ['sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors_boost_python.hpp',
    14761476                         'sage/quadratic_forms/enumerate_short_vectors/enumerate_short_vectors.hpp'],
    14771477              language = 'c++',
    1478               extra_compile_args=['-std=c++11'],
     1478              extra_compile_args=["-std=c++0x"],
    14791479              include_dirs = [SAGE_INC, SAGE_INC + '/python2.7', 'sage/c_libs/include'],
    1480               libraries = ['stdc++', 'boost_python', 'mpfi', 'mpfr', 'gmp']),
     1480              libraries = ['stdc++', 'boost_python-2.7', 'mpfi', 'mpfr', 'gmp']),
    14811481
    14821482    Extension('sage.quadratic_forms.quadratic_form__evaluate',
    14831483              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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 5 years ago by tmonteil

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 5 years ago by mraum

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 5 years ago by malb

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

comment:8 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 4 years ago by cremona

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 4 years ago by cremona

  • Cc akoutsianas added
Note: See TracTickets for help on using tickets.