Opened 9 years ago

Closed 9 years ago

#15760 closed enhancement (fixed)

Speed up short vector enumeration

Reported by: Jeroen Demeyer Owned by:
Priority: major Milestone: sage-6.2
Component: performance Keywords:
Cc: Martin Raum, Peter Bruin Merged in:
Authors: Jeroen Demeyer Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: u/jdemeyer/ticket/15760 (Commits, GitHub, GitLab) Commit: 7081e42db98d67260a1b7754a59093d006123d0b
Dependencies: Stopgaps:

Status badges

Description (last modified by Jeroen Demeyer)

The short_vector_list_up_to_length method of quadratic forms uses GP but the interface is so badly done that the majority of the time is taken up by the Sage interface, and not by the actual computation. Still, even with the new implementation, most time is taken by the conversion from PARI to Sage vectors.

Timings before:

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.13 s per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 6.74 s per loop

Timings 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)
10 loops, best of 3: 34.4 ms per loop
sage: %timeit qf.short_vector_list_up_to_length(1000)
1 loops, best of 3: 1.03 s per loop

Change History (13)

comment:1 Changed 9 years ago by Jeroen Demeyer

Description: modified (diff)

comment:2 Changed 9 years ago by Jeroen Demeyer

Branch: u/jdemeyer/ticket/15760
Created: Jan 29, 2014, 10:37:53 AMJan 29, 2014, 10:37:53 AM
Modified: Jan 29, 2014, 12:50:06 PMJan 29, 2014, 12:50:06 PM

comment:3 Changed 9 years ago by Jeroen Demeyer

Commit: 8c1245926c73f1692dbdd2d3da07dacb7b6e50b5
Description: modified (diff)

New commits:

8c12459Speed up short_vector_list_up_to_length()

comment:4 Changed 9 years ago by git

Commit: 8c1245926c73f1692dbdd2d3da07dacb7b6e50b53e80bfdc75d89f154a41e815b004e19207422f76

Branch pushed to git repo; I updated commit sha1. New commits:

3e80bfdSome "long time" fixes in quadratic forms

comment:5 Changed 9 years ago by Jeroen Demeyer

Cc: Martin Raum added
Status: newneeds_review

comment:6 Changed 9 years ago by Jeroen Demeyer

Cc: Peter Bruin added

comment:7 Changed 9 years ago by Peter Bruin

Reviewers: Peter Bruin

Looks good and I can confirm the speed-up. Now doctesting...

comment:8 Changed 9 years ago by Peter Bruin

Status: needs_reviewpositive_review

comment:9 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:10 Changed 9 years ago by Volker Braun

OSError: [quadratic] /scratch/buildbot/sage/redhawk-1/sage_git/build/local/lib/python2.7/site-packages/sage/quadratic_forms/quadratic_form.py:docstring of sage.quadratic_forms.quadratic_form.QuadraticForm.short_vector_list_up_to_length:8: WARNING: Inline literal start-string without end-string.

I think thats you ;-)

comment:11 Changed 9 years ago by git

Commit: 3e80bfdc75d89f154a41e815b004e19207422f767081e42db98d67260a1b7754a59093d006123d0b
Status: positive_reviewneeds_review

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

7081e42Fix documentation syntax

comment:12 Changed 9 years ago by Peter Bruin

Status: needs_reviewpositive_review

comment:13 Changed 9 years ago by Volker Braun

Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.