Opened 7 years ago

Closed 6 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:

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 6 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by mraum

  • Status changed from new to needs_review

comment:2 Changed 6 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 6 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 6 years ago by mraum

comment:4 Changed 6 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 6 years ago by mraum

  • Description modified (diff)
  • Report Upstream changed from N/A to Workaround found; Bug reported upstream.

comment:6 Changed 6 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 6 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

Thanks!

comment:8 Changed 6 years ago by vbraun

  • Description modified (diff)

comment:9 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.7.beta3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.