Opened 10 years ago

Closed 10 years ago

#13531 closed defect (fixed)

short_vector_list_up_to_length is slow and wrong

Reported by: mraum Owned by: justin
Priority: major Milestone: sage-5.7
Component: quadratic forms Keywords:
Cc: Merged in: sage-5.7.beta3
Authors: Martin Raum Reviewers: Volker Braun
Report Upstream: Workaround found; Bug reported upstream. Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by vbraun)

  1. The method short_vector_list_up_to_length does not return a list of vectors as claimed in the documentation.
  2. Even with lattices of rank 6 and determinant 3 it takes really long to get the result. This is not PARI's fault (which is called in the background), but pexpect's.
  3. In some cases no result will be returned because to many GP queries are performed. This exceeds the maximal number of GP's sage[...] variables.

All this is fixed (the speed only in parts) by the attached patch.

This is PARI Bug#1394, fixed upstream in commit 2d4455dc481cc0f0b09900e97c4fbb2e87b8db4d.

Apply trac_13531-short_vectors-v2.patch

Attachments (1)

trac_13531-short_vectors-v2.patch (6.2 KB) - added by mraum 10 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 10 years ago by mraum

Status: newneeds_review

comment:2 Changed 10 years ago by mraum

I had to make even further changes, since Pari sometimes returns incorrect results. I will send a report to upstream, and I have built in a work around for the moment. For the record, I reproduce the corresponding example here.

qf = [72, 12; 12, 120];
vecs = qfminim(qf, 2*22953421 - 2);
matsize(vecs[3])
for(i=1,matsize(vecs[3])[2],if(72 * vecs[3][1,i]^2 + 24 * vecs[3][1,i]*vecs[3][2,i] + 120 * vecs[3][2,i]^2 > 2*22953421 - 2, print(vecs[3][,i])))

gives the following:

[-65, 623]~
[-143, 623]~
[-44, 622]~
[-16, 620]~
[-220, 617]~
[-243, 614]~
[65, 610]~
[77, 608]~
[-285, 607]~
[-300, 604]~
[-361, 589]~
[-381, 583]~
[220, 573]~
[-411, 573]~
[-422, 569]~
[247, 564]~
[-435, 564]~
[-445, 560]~
[285, 550]~
[300, 544]~
[312, 539]~
[-515, 527]~
[348, 523]~
[-548, 508]~
[407, 493]~
[416, 488]~
[423, 484]~
[435, 477]~
[-594, 477]~
[445, 471]~
[-602, 471]~
[-611, 464]~
[504, 432]~
[-648, 432]~
[515, 424]~
[519, 421]~
[523, 418]~
[536, 408]~
[-672, 408]~
[557, 391]~
[-699, 377]~
[591, 361]~
[-715, 356]~
[-720, 349]~
[633, 319]~
[-744, 311]~
[-749, 302]~
[-763, 274]~
[681, 262]~
[684, 258]~
[-770, 258]~
[-774, 248]~
[715, 213]~
[-786, 213]~
[720, 205]~
[723, 200]~
[726, 195]~
[-791, 195]~
[-792, 191]~
[734, 181]~
[741, 168]~
[-797, 168]~
[752, 146]~
[758, 133]~
[764, 119]~
[-804, 115]~
[770, 104]~
[773, 96]~
[-805, 96]~
[-805, 65]~
[-804, 46]~
[-803, 34]~
[796, 14]~
[798, 3]~
[-799, 3]~

comment:3 Changed 10 years ago by vbraun

Can you add a doctests for the Pari bug and a link to the upstream bug report? Presumably we'll want to remove your workaround when it is fixed.

Changed 10 years ago by mraum

comment:4 Changed 10 years ago by mraum

The test for the too long vectors is marked long time, because on my system it takes about 140 seconds. Currently, this is the best example I have.

I have looked for the bug report, and I can't find it. I might have forgotten to send it, so I have just sent it. I post the bug number as soon as possible.

comment:5 Changed 10 years ago by mraum

Description: modified (diff)
Report Upstream: N/AWorkaround found; Bug reported upstream.

comment:6 Changed 10 years ago by mraum

Description: modified (diff)

I got this reply:

it seems this bug has disappeared in the development branch in rev 2d4455dc:

commit 2d4455dc481cc0f0b09900e97c4fbb2e87b8db4d

Author: Karim Belabas <Karim.Belabas@…>

Date: Sun Jul 17 11:27:48 2011 +0000

minor cleanup minim0()

comment:7 Changed 10 years ago by vbraun

Reviewers: Volker Braun
Status: needs_reviewpositive_review

Thanks!

comment:8 Changed 10 years ago by vbraun

Description: modified (diff)

comment:9 Changed 10 years ago by jdemeyer

Merged in: sage-5.7.beta3
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.