Opened 12 years ago

Closed 8 months ago

Last modified 8 months ago

#5178 closed enhancement (fixed)

Make LLL_gram also work with Gram matrices with non-integer entries

Reported by: was Owned by: was
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by slelievre)

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 orientation-preserving.

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 non-integral 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)

trac_5178.patch (5.9 KB) - added by was 12 years ago.

Download all attachments as: .zip

Change History (23)

Changed 12 years ago by was

comment:1 Changed 12 years ago by was

Gonzalo Tornaria sent this review in email to me:

Looks good to me.

However, it seems pari is hanging when using lllgram() on some
matrices with rational or integer entries; maybe indefinite or
semidefinite matrices are the issue.
Moreover, sage hangs badly on this...

E.g.

sage: pari("[1,1;1,1/2]").qflllgram()

(it also hangs when running equivalent command from gp, Ctrl-C stops
gp but not sage).
[equivalent command = qflllgram([1,1,1,1/2])

However, using 0.5 instead of 1/2 works ok.

Seems a bug in pari, but it was not exposed in sage's LLL_gram() before.

Gonzalo

He does point out that bad things can happen, but that the bugs are in PARI, not the new code attached to this patch.

comment:2 Changed 12 years ago by boothby

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 boothby

  • Summary changed from [with patch; needs review] change LLL_gram to work with Gram matrices with not-necessarily integer entries to [with patch; review] change LLL_gram to work with Gram matrices with not-necessarily 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 mabshoff

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 sage-nt I guess.

Cheers,

Michael

comment:5 Changed 12 years ago by ncalexan

  • Summary changed from [with patch; review] change LLL_gram to work with Gram matrices with not-necessarily integer entries to [with patch, needs review] change LLL_gram to work with Gram matrices with not-necessarily 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 craigcitro

  • Summary changed from [with patch, needs review] change LLL_gram to work with Gram matrices with not-necessarily integer entries to [with patch, needs work (doc cleanup)] change LLL_gram to work with Gram matrices with not-necessarily 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 boothby

  • Report Upstream set to N/A

Just got an email from Bill Allombert regarding this bug:

Hello,
PARI 2.5.0-stable 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 boothby

  • 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 boothby

  • 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 boothby

  • Status changed from new to needs_review

comment:11 Changed 10 years ago by boothby

  • Status changed from needs_review to needs_work

comment:12 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:15 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:16 Changed 8 months ago by slelievre

  • 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 sage-6.4 to sage-9.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 not-necessarily integer entries to Make LLL_gram also work with Gram matrices with non-integer entries

Turned the 2009 patch into a branch based on Sage 9.2.beta12.

Please review.


New commits:

c72be005178: LLL for Gram matrices beyond ZZ

comment:17 Changed 8 months ago by slelievre

  • Authors set to William Stein, Samuel Lelièvre
  • Cc cremona kohel malb added

comment:18 Changed 8 months ago by malb

  • Reviewers set to Martin Albrecht
  • Status changed from needs_review to positive_review

Looks good to me

comment:19 Changed 8 months ago by slelievre

  • 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 follow-up ticket.

comment:20 Changed 8 months ago by slelievre

Possible follow-up improvements:

  • Add optional parameter force_orientation_preserving=True. Setting it to False 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 cross-references in the documentation to/from any similar methods, e.g. provided by fplll.

comment:21 Changed 8 months ago by vbraun

  • 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 slelievre

  • Commit c72be0054532d77b67df23ed9750827a6a656a39 deleted

Follow-up at #30678.

Note: See TracTickets for help on using tickets.