Skip to content

Very slow computation time compared to other methods #300

Description

@Wulfhartus

Hi,
I'm trying to compute short vectors of thousands of lattices in small dimension using SageMaths (Jupyter) on Windows 11.
I tried the function SVP as used in the example files:

from fpylll import LLL, IntegerMatrix, SVP
A = IntegerMatrix.from_matrix([
    [-1, -1,  0, -2,  0,  0, -1,  0,  1,  1, -1],
    [ 2,  0,  0,  0,  1,  0, -1,  1,  0,  2,  1],
    [ 0, -1, -2,  2,  0,  0,  0, -2,  2, -1, -1],
    [-1, -1, -1,  1,  1, -1,  2,  0,  2, -1,  2],
    [-1,  1, -1,  0,  1,  2, -2,  1, -1,  2, -1],
    [-1,  1, -1, -1,  0,  0,  1,  3,  0,  0, -2],
    [ 1,  0,  0,  0,  0,  1, -2,  1,  0, -3, -1],
    [-2, -2,  0,  2, -1,  0,  0,  1,  0,  2,  0],
    [-1,  3,  1,  1,  1, -2,  0,  0,  1,  1,  2],
    [-1,  1,  3,  2,  1,  1,  2,  0,  2,  0, -1],
    [ 0,  2,  1,  0, -3,  3, -1,  1,  3, -1, -1],
])
t=time.time()   
u=SVP.shortest_vector(A, method='proved')
print(time.time()-t,'s')

The time taken is flabbergastingly long : 0.39350318908691406 s.

I have another method, using Fincke-Pohst algorithm implemented in PariGP (qfminim) and that can be used within Sage. Its execution time takes 0.0020112991333007812 s. I wonder why fpylll is so much slower than this.

Why is fpylll so slow and how to get it to work faster ?

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions