[with patch, needs work (doc cleanup)] change LLL_gram to work with Gram matrices with not-necessarily integer entries

[was]

This patch changes LLL_gram to work with Gram matrices with not-necessarily integer entries. Also it fixes several "non-optimal" coding issues both in the old implementation and the doctests. For example, instead of computing U.det() to determine if the unimodular A has det -1 or 1, we just compute A.change_ring(GF(3)).det(), which is much faster.

Changing LLL_gram to work for nonintegral gram matrices is critical for applications to computing class groups for the course I'm teaching right now.

[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.

[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.

[boothby]

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

[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

[ncalexan]

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.

[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. 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?

[boothby]

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.

[boothby]

oops, didn't realize changing the "upstream" field would close the ticket