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:  sage6.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: 
Description (last modified by )
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
Description:  modified (diff) 

comment:2 Changed 9 years ago by
Branch:  → u/jdemeyer/ticket/15760 

Created:  Jan 29, 2014, 10:37:53 AM → Jan 29, 2014, 10:37:53 AM 
Modified:  Jan 29, 2014, 12:50:06 PM → Jan 29, 2014, 12:50:06 PM 
comment:3 Changed 9 years ago by
Commit:  → 8c1245926c73f1692dbdd2d3da07dacb7b6e50b5 

Description:  modified (diff) 
comment:4 Changed 9 years ago by
Commit:  8c1245926c73f1692dbdd2d3da07dacb7b6e50b5 → 3e80bfdc75d89f154a41e815b004e19207422f76 

Branch pushed to git repo; I updated commit sha1. New commits:
3e80bfd  Some "long time" fixes in quadratic forms

comment:5 Changed 9 years ago by
Cc:  Martin Raum added 

Status:  new → needs_review 
comment:6 Changed 9 years ago by
Cc:  Peter Bruin added 

comment:7 Changed 9 years ago by
Reviewers:  → Peter Bruin 

Looks good and I can confirm the speedup. Now doctesting...
comment:8 Changed 9 years ago by
Status:  needs_review → positive_review 

comment:9 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:10 Changed 9 years ago by
OSError: [quadratic] /scratch/buildbot/sage/redhawk1/sage_git/build/local/lib/python2.7/sitepackages/sage/quadratic_forms/quadratic_form.py:docstring of sage.quadratic_forms.quadratic_form.QuadraticForm.short_vector_list_up_to_length:8: WARNING: Inline literal startstring without endstring.
I think thats you ;)
comment:11 Changed 9 years ago by
Commit:  3e80bfdc75d89f154a41e815b004e19207422f76 → 7081e42db98d67260a1b7754a59093d006123d0b 

Status:  positive_review → needs_review 
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
7081e42  Fix documentation syntax

comment:12 Changed 9 years ago by
Status:  needs_review → positive_review 

comment:13 Changed 9 years ago by
Resolution:  → fixed 

Status:  positive_review → closed 
Note: See
TracTickets for help on using
tickets.
New commits:
Speed up short_vector_list_up_to_length()