#5178 closed enhancement (fixed)
Make LLL_gram also work with Gram matrices with noninteger entries
Reported by:  was  Owned by:  was 

Priority:  major  Milestone:  sage9.2 
Component:  linear algebra  Keywords:  LLL, Gram 
Cc:  boothby, craigcitro, cremona, kohel, mabshoff, malb, ncalexan, slelievre, tornaria, was  Merged in:  
Authors:  William Stein, Samuel Lelièvre  Reviewers:  Gonzalo Tornaría, Craig Citro, Martin Albrecht 
Report Upstream:  Fixed upstream, in a later stable release.  Work issues:  
Branch:  c72be00 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket is to make LLL_gram
work with more general
Gram matrices than integer ones.
It also speeds up the step where we check the transformation matrix is orientationpreserving.
The trick for the speedup is computing a determinant mod 3
instead of in ZZ
: given a matrix U
over ZZ
with
determinant known to be 1 or 1, checking whether it is
+1 or 1 is much faster with U.change_ring(GF(3)).det()
than with U.det()
.)
Making LLL_gram
work for nonintegral Gram matrices
is critical for applications to computing class groups.
That was used in a course William Stein taught in 2009,
at which time he wrote the patch trac_5178.patch
attached to this ticket.
Gonzalo Tornaría observed the patch revealed a PARI bug. The PARI bug was fixed.
This ticket adapts William Stein's 2009 patch to Sage 9.x.
Early discussion of using this function for matrices over the reals and not just the integers:
Attachments (1)
Change History (23)
Changed 12 years ago by
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
I reported the bug upstream. Is Gonzalo's +1 good enough? I'm not really comfortable with LLL enough to sign off on this.
comment:3 Changed 12 years ago by
 Summary changed from [with patch; needs review] change LLL_gram to work with Gram matrices with notnecessarily integer entries to [with patch; review] change LLL_gram to work with Gram matrices with notnecessarily integer entries
Email from Bill Allombert in response to the bug:
Hello, This problem does not occurs with PARI 2.4.3. This seems to be another instance of bug #505 which was fixed in PARI 2.4.1 as 1 qflll / qflllgram (t_MAT with t_FRAC entries) would not reduce to the integer case (> insufficient precision, SEGV) [#505] The fix should probably be backported. Thanks for your bug report, Bill
comment:4 Changed 12 years ago by
So, it this a positive review then?
Nick did ping me last night about updating to pari 2.4.3svn sources and it seems that we don't really have a choice any more. But this issue should be raised on sagent I guess.
Cheers,
Michael
comment:5 Changed 12 years ago by
 Summary changed from [with patch; review] change LLL_gram to work with Gram matrices with notnecessarily integer entries to [with patch, needs review] change LLL_gram to work with Gram matrices with notnecessarily integer entries
Can we get some movement on this? I don't think an updated pari is happening anytime soon but it would be nice to close this.
comment:6 Changed 12 years ago by
 Summary changed from [with patch, needs review] change LLL_gram to work with Gram matrices with notnecessarily integer entries to [with patch, needs work (doc cleanup)] change LLL_gram to work with Gram matrices with notnecessarily integer entries
This looks good. The only objection I have is that the documentation isn't correctly formatted for sphinx  in particular, the various sections of the docstring (like EXAMPLES
) should have a double colon, and there should be more blank lines to get things to format correctly. Also, one or two more examples with noninteger entries in the docstring wouldn't hurt, if you're already there. Maybe something from a class group computation, even if it requires # long
?
comment:7 Changed 10 years ago by
 Report Upstream set to N/A
Just got an email from Bill Allombert regarding this bug:
Hello, PARI 2.5.0stable was released with a fix for this problem, closing this report. Thanks for using our bug tracking system, Cheers, Bill.
comment:8 Changed 10 years ago by
 Report Upstream changed from N/A to Fixed upstream, in a later stable release.
 Resolution set to fixed
 Status changed from needs_work to closed
comment:9 Changed 10 years ago by
 Resolution fixed deleted
 Status changed from closed to new
oops, didn't realize changing the "upstream" field would close the ticket
comment:10 Changed 10 years ago by
 Status changed from new to needs_review
comment:11 Changed 10 years ago by
 Status changed from needs_review to needs_work
comment:12 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:13 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:14 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:15 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:16 Changed 8 months ago by
 Branch set to public/ticket/5178
 Cc boothby craigcitro mabshoff ncalexan slelievre tornaria was added
 Commit set to c72be0054532d77b67df23ed9750827a6a656a39
 Description modified (diff)
 Keywords LLL Gram added
 Milestone changed from sage6.4 to sage9.2
 Status changed from needs_work to needs_review
 Summary changed from [with patch, needs work (doc cleanup)] change LLL_gram to work with Gram matrices with notnecessarily integer entries to Make LLL_gram also work with Gram matrices with noninteger entries
Turned the 2009 patch into a branch based on Sage 9.2.beta12.
Please review.
New commits:
c72be00  5178: LLL for Gram matrices beyond ZZ

comment:17 Changed 8 months ago by
 Cc cremona kohel malb added
comment:18 Changed 8 months ago by
 Reviewers set to Martin Albrecht
 Status changed from needs_review to positive_review
Looks good to me
comment:19 Changed 8 months ago by
 Reviewers changed from Martin Albrecht to Gonzalo Tornaría, Craig Citro, Martin Albrecht
Replying to craigcitro:
This looks good. The only objection I have is that the documentation isn't correctly formatted for sphinx  in particular, the various sections of the docstring (like
EXAMPLES
) should have a double colon, and there should be more blank lines to get things to format correctly.
Addressed in the branch.
Also, one or two more examples with noninteger entries in the docstring wouldn't hurt, if you're already there. Maybe something from a class group computation, even if it requires
# long
?
I agree. William, would you have a few examples from your course?
Since Martin already gave positive review (thanks!), adding examples could be done in a followup ticket.
comment:20 Changed 8 months ago by
Possible followup improvements:
 Add optional parameter
force_orientation_preserving=True
. Setting it toFalse
when calling the method would skip the last part (that checks whether the determinant is 1 or 1 and changes the sign of the last column in case it is 1) and save some time.
 Maybe PARI has an option to force returning a determinant 1 transformation matrix? If so, use it.
 Add crossreferences in the documentation to/from any similar methods, e.g. provided by fplll.
comment:21 Changed 8 months ago by
 Branch changed from public/ticket/5178 to c72be0054532d77b67df23ed9750827a6a656a39
 Resolution set to fixed
 Status changed from positive_review to closed
comment:22 Changed 8 months ago by
 Commit c72be0054532d77b67df23ed9750827a6a656a39 deleted
Followup at #30678.
Gonzalo Tornaria sent this review in email to me:
He does point out that bad things can happen, but that the bugs are in PARI, not the new code attached to this patch.